Big O notation algebra

Question

I have a couple of questions regarding some algebra using big O notation:

if f(n)=O(g(n))

is log(f(n)) = O(log(g(n)))?

is N^{f(n)}=O(N^{g(n)})? (where N is any real number)

Answer 1

• Is log(f(n)) = O(log(g(n))) ? No, it is not essential, for example:

  f(n)= n and g(n) = n^2. Here f(n) = O(g(n))

• Is N^{f(n)}=O(N^{g(n)}) ? No, this is also not true as

for two algorithms , the ratio may remain constant, but the ratio of each raised to certain power will never be constant.

Take

f ( n ) = 2 n and g ( n ) = n .

It is true that 2n is O(n). But consider

This limit is not bounded - it goes to infinity as n goes to infinity. So,

2^2n is not O(2n) i.e. 2f(n) is not O(2g(n)) in this case.