recategorized by
15,376 views
45 votes
45 votes

Consider the following two functions:

$g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n > 10,000 \end{cases}$

$g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}$

Which of the following is true?

  1. $g_1(n) \text{ is } O(g_2(n))$

  2. $g_1(n) \text{ is } O(n^3)$

  3. $g_2(n) \text{ is } O(g_1(n))$

  4. $g_2(n) \text{ is } O(n)$

recategorized by

6 Answers

Best answer
71 votes
71 votes
For asymptotic complexity, we assume sufficiently large $n$. So, $g_1(n) = n^2$ and $g_2(n) = n^3$. Growth rate of $g_1$ is less than that of $g_2$, i.e., $g_1(n) = O(g_2(n)).$

Options $A$ and $B$ are TRUE here.
edited by
17 votes
17 votes

The answer is given...Here is the answer...

7 votes
7 votes

Yes. Both (a) and (b) are correct. $n^{2}$ is $O(n^{3})$.

edited by
1 votes
1 votes
Index Condition $g_{1}(n)$ $g_{2}(n)$ Time Complexity($B$) Time Complexity($A$)
1 $0 \leq n \leq 100$ $n^{3}$ $n$ $O(n^{3})$ $O(g^{2}(n))$ -- Fails
2 $101 \leq n \leq 10000$ $n^{3}$ $n^{3}$ $O(n^{3})$ $O(g^{2}(n))$
3 $n \geq 10001$ $n^{2}$ $n^{3}$ $O(n^{3})$ $O(g^{2}(n))$

Thus the right option should be B

edited by
Answer:

Related questions

19 votes
19 votes
3 answers
4
Kathleen asked Oct 5, 2014
2,694 views
What function of $x$, $n$ is computed by this program?Function what(x, n:integer): integer: Var value : integer begin value := 1 if n 0 then begin if n mod 2 =1 then val...