Show that g(n) is O(g(n)) for each of the following

Question

2^(sqrt(log(n)) is O(n(^4/3))

n^(4/3) is O(n(log(n))^3)

n(log(n))^3) is O(n^(log(n))

n^(log(n)) is O(2^n)

I can do it for them when they have the same base; I can't figure it out when they don't have the same base--I know that these are all true.

Answer 1

Take log on both sides, for each of them. This is permitted because log is a monotonically increasing function