Search code examples
big-oproof

Show that n^2 is not O(n*log(n))?

Using only the definition of O()?

Solution

  • You need to prove by contradiction. Assume that n^2 is O(n*log(n)). Which means by definition there is a finite and non variable real number c such that 

    n^2 <= c * n * log(n)

    for every n bigger than some finite number n0.

    Then you arrive to the point when c >= n /log(n), and you derive that as n -> INF, c >= INF which is obviously impossible.

    And you conclude n^2 is not O(n*log(n))