n^2 log n complexity

Question

I am just a bit confused. If time complexity of an algorithm is given by

what is that in big O notation? Just or we keep the log?

Answer 1

If that's the time-complexity of the algorithm, then it is in big-O notation already, so, yes, keep the log. Asymptotically, there is a difference between O(n^2) and O((n^2)*log(n)).

Answer 2

A formal mathematical proof would be nice here.

Let's define following variables and functions:
N - input length of the algorithm,
f(N) = N^2*ln(N) - a function that computes algorithm's execution time.

Let's determine whether growth of this function is asymptotically bounded by O(N^2).

According to the definition of the asymptotic notation [1], g(x) is an asymptotic bound for f(x) if and only if: for all sufficiently large values of x, the absolute value of f(x) is at most a positive constant multiple of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= M*g(x) for all x >= x0 (1)

In our case, there must exists a positive real number M and a real number N0 such that: |N^2*ln(N)| <= M*N^2 for all N >= N0 (2)

Obviously, such M and x0 do not exist, because for any arbitrary large M there is N0, such that ln(N) > M for all N >= N0 (3)

Thus, we have proved that N^2*ln(N) is not asymptotically bounded by O(N^2).

References:
1: - https://en.wikipedia.org/wiki/Big_O_notation