1

What does it mean when there is an addition of functions inside of the Big O, e.g. O(n + nlogn). Would this be different than O(nlogn) since it is the bigger function?

Raulito28
  • 49
  • 1
  • 8
  • 1
    No, it would be the same. You need to leave multiple functions inside when they depend on different parameters though, e.g. `O(n+m^3)` – makhan Apr 14 '15 at 04:25

1 Answers1

0

With asymptotic notation, you are effectively trying to set a bound that you know your algorithm will not cross. Big-O is the worst that your algorithm will perform. In your case, O(n + log(n)) turns into O(nlog(n)) because nlog(n) grows the fastest as n approaches infinity. This is why you are usually taught that you can discount the smaller function, at least when measuring Big-O. There are also Big-Theta (what your average run-time will be) and Big-Omega (the best case scenario).

Waimeh
  • 1
  • 4