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?
Asked
Active
Viewed 254 times
1 Answers
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