Search code examples
c++algorithmmaththeorem-proving

How to prove Big O notation

In my algorithm class we are discussing big O notation and I am stuck proving this example problem:

Prove f(n) = 3n lg n + 10n + lg n + 20 = O(n lg n)

Details will be appreciated.

Solution

  • Big O notation is an asymptotic notation and it's all about approximation of cases (worst, best and mid one).
    In your example, nlgn grows faster than both n and lgn, moreover constant values are not relevant and can be ignored in such an approximation.
    Because of that, it follows that the complexity is O(nlgn).