-3

What is the Big oh of n^2+nlog(n)? prove your answer. How do I choose the big oh notation is it n^2 or nlog(n) what is the strategy to choose?

and if I choose nlog(n) how would I solve it?

Reem
  • 1
  • 2
  • 1
    Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Caleth Sep 24 '18 at 13:47
  • I'm voting to close this question as off-topic because it's purely a mathematical question. – Bernhard Barker Sep 24 '18 at 15:06
  • Duplicate on [math.se] - [How do I show a function is Big-O of another function using the definition of Big-O?](https://math.stackexchange.com/questions/1173739/how-do-i-show-a-function-is-big-o-of-another-function-using-the-definition-of-bi) – Bernhard Barker Sep 24 '18 at 15:07
  • Also, [How to prove this statement of big o notation?](https://stackoverflow.com/questions/2667703/how-to-prove-this-statement-of-big-o-notation) – Bernhard Barker Sep 24 '18 at 15:14

1 Answers1

0

You seem to know that when you sum two functions, the Big O is the Big O of the "larger" function (for arbitrarily large n), so we just need to find which of the two functions that is. To do this, we can solve the following limit:

  lim (n -> inf) n^2 / nlog(n)
= lim (n -> inf) n / log(n)
= lim (n -> inf) 1 / (1 / n) (L'Hopital's Rule)
= inf

This proves that n^2 is the "larger" function, and so O(n^2 + nlog(n)) = n^2

Note that you also could have shown that:

lim (n -> inf) nlog(n) / n^2 = 0
aoldershaw
  • 131
  • 1
  • 3
  • So when I solve big O I always have to choose the bigger one ! can you lead me to a stable structure for choosing big o like a table maybe ? – Reem Sep 24 '18 at 14:01