log n^2
is equivalent to 2logn
which grows at the same rate as logn
, as I disregard the factors and constants. but if I was to square the whole term so that I end up with (logn)^2
is it also big theta of logn
?
No. If f is any unbounded function then f(n)^2 is not O(f).
Because f(n)^2 = O(f) means there's a c and N such that n > N implies f(n)^2 <= cf(n). Which implies f(n) <= c, and so f is bounded.
log(n) is unbounded, so log(n)^2 is not O(log(n)).