When we calculate Big O, is nlogn the same as n^2logn^2 ?(basically when n is replaced with n square)

I was discussing this today with a colleague who mentioned the nlogn complexity of an algorithm is same when n becomes n^2.

That does not sound correct. Looking for expert opinions.

CodePudding user response：

No, it is not true. You can look at the ratio of two functions and evaluate asymptotic limit

n^2*log(n^2) = 2*n^2*log(n)  (note that log(n^2) has the same oder as log(n))
ratio = [n*log(n)] / [2*n^2*log(n)] = 1/(2*n)

When n becomes larger, ratio tends to zero, so n*log(n) has lower order than n^2*log(n^2)

CodePudding user response：

Your friend is probably thinking of the fact that O(log n²) = O(log n). This means that O(n log n²) = O(n log n) and O(n² log n²) = O(n² log n); but it does not mean that O(n² log n²) = O(n log n).

CodePudding user response：

No, that's clearly not correct.

Probably what your friend is confused by is that exponents inside a logarithm can be turned into multipliers: log n² = 2 log n. This means that O(log n²) = O(2 log n), and since multiplicative constants are dropped inside Big-O, O(2 log n) = O(log n).

As a rule of thumb, in Big-O analysis exponents inside logarithms can be discarded. This doesn't apply to regular non-logarithmic squaring, though.

• O(log n²) = O(log n)
• O(n²) ≠ O(n)
• O(n² log n) ≠ O(n log n)
• O(n² log n²) = O(n² log n) ≠ O(n log n)

CodePudding user response：

we can take the below order for big - oh

1<log n<root n<n<n log n<n^2<n^3<......2^n<3^n<....<n^n.

from this n^2 is one of the upper bound of n. So Big oh of n and n2 can't be the same.