The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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 \geq 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)$


asked in Algorithms by Veteran (69k points) | 1.2k views

3 Answers

+24 votes
Best answer
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.
answered by Veteran (346k points)
selected by
i think only a is correct in second option they might be mentioning the time complexity of g1 itself which is not O(n^3) it is O(n^2) for n>=10000 i.e. high value of n
@harit  g1  value is (n^2) for n>=10000 so we can say g1  is asymptotically O(n^3)

Sir please verify answer given by  Avik10 

why not O(n^2)  it will be asymptotically tighter  then O(n^3)
$O(n^2)$ is also correct.
+5 votes

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

answered by Veteran (18k points)
edited by
I though so but when paper says select the correct(only one) choice then it creates doubt!
+1 vote
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


answered by (383 points)
edited by
Make this best answer
This is wrong; big-O cares for only large $n$.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,713 questions
40,262 answers
38,894 users