0

Why do we just take the highest degree of polynomial for Big Oh notation. I understand that we can drop the constants as they won't matter for a very high value of 'n'.

But, say an algorithm takes (nlogn + n) time, then why do we ignore 'n' in this case. And the big Oh comes out to be O(nlogn).
Big Oh has to be the upper bound of time taken by the algorithm. So, shouldn't it be (nlogn + n), even for very high values of n?

Ankit Singodia
  • 581
  • 1
  • 6
  • 16
  • 4
    Because eventually the *log(n)* will be greater than whatever constant is put before *n*, so *n log n* will "overtake" *n*, hence it is irrelevant. – Willem Van Onsem Jan 18 '19 at 15:39
  • 2
    The exact same logic as for constant applies to lower order terms of `n`. – luk2302 Jan 18 '19 at 15:40
  • The Big O represent the variation for what I understand of it. This is why you don't see O(2n). However I guess you could see O(nlog(n)+nm) for a two elements... right? – Toady Jan 18 '19 at 15:42
  • 2
    What does this have to do with java? – Joseph Wood Jan 18 '19 at 16:24
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic), [how to ask](http://stackoverflow.com/help/how-to-ask), and [... the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. – Prune Jan 18 '19 at 16:44

2 Answers2

8

Because O is asymptotic comparison which answers the question how the function compare for large n. Lower degrees of polynomial become insignificant for function behavior once n is sufficiently large.

Karol Dowbecki
  • 43,645
  • 9
  • 78
  • 111
3

One way to see that is: "nlog(n) + n" is smaller than "2nlog(n)". Now you can drop the 2.

Marco
  • 479
  • 4
  • 10