0
$\begingroup$

A. $f(n)=10 n^2, \ g(n)= n^2+100.$

B. $f (n)= n^{\frac53} ,\ g(n)= n^{\frac n2}.$

Assume that the pairs of functions $f(n)$ and $g(n)$ of the above Problem correspond to the running times of two different algorithms A and B, respectively, for solving a given problem when the input size is $n$ (do not worry about the fact that some of the instances do not represent real problems). Determine, for each pair of functions, the problem sizes for which Algorithm A is better than Algorithm B.

## I don't know what exactly want from these question ,is he want explain theory or time complexity for both ?

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

You are given the run time for two algorithms by $f$ and $g$. In general you cannot say which algorithm is better: The first algorithm might be faster for samll instances but slow for large instances, and the second algorithm the other way around.

Consider the two functions given in A. For $n = 1$ you get $f(n) = 10$ and $g(n) = 101$. Thus, for small instances $f$ seems be faster than $g$. However, for $n = 10$ you get $f(n) = 1000$ and $g(n) = 200$. So it seems that for larger instances $f$ is slower than $g$. Your task is to compute the boundary where $f$ and $g$ have (almost) the same run time and say which one is better for instances of smaller size than this boundary and which one is better for instances of greater size than the boundary. Note that it can also happen that there are several boundaries.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.