Search code examples
algorithmasymptotic-complexity

if log n^2 is big theta of log n , is (logn)^2 also big theta of logn?


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?


Solution

  • 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)).