What should be the Big O of f(n) = n^5 + 2^log(n)?

Question

I came across a problem where I've to select the correct Big O for the function f(n) = n^5 + 2^log(n)... I tried putting large values and found out that n^5 grows significantly as compare to 2^log(n)... But then someone told me that exponential functions grow significantly as compared to other functions... And I got confused again... To be honest I think 2^log(n) is not an exponential function... But because of my weak logarithmic concepts, I am unable to prove that...

I just want someone to tell me that yes n^5 is larger than 2^log(n) so that I can prove that 2^log(n) is not an exponential function...

Thanks in advance. :)

I just want someone to tell me that yes n^5 is larger than 2^log(n) so that I can prove that 2^log(n) is not an exponential function...

Thanks in advance. :)

user_5538420 · Answer

2^log(n) = (2/e)^log(n) * e^log(n) = a^log(n) * n where a = 2/e < 1 (assuming log is the natural logarithm).

It follows that f(n) = n^5 + 2^log(n) < n^5 + n and therefore f(n) = O(n^5).

[ EDIT ] In the general case of logarithms of an arbitrary base b, using that 2 = b^log_b(2) it follows that:

    2^log_b(n) = (b^log_b(2))^(log_b(n))
               = b^(log_b(2)*log_b(n))
               = (b^log_b(n))^log_b(2)
               = n^log_b(2)
               = n^(1/log_2(b))

Therefore f(n) = n^5 + log_b(n) = O( n^5 + n^(1/log_2(b)) ) = O( n^max(5, 1/log_2(b)) ).

In particular, f(n) = O(n^5) for log_2(b) > 1/5 ⇔ b > 2^(1/5), which covers the common log bases of 2, e, 10.

user_1756636 · Answer

O(2^logn)=O(n) - this follows straight from the definition of logarithm.

More formally:

f(n)=2^logn

log₂f(n)=log₂(2^logn)=lognlog₂2=log₂n ==>f(n)=n

==> O(2^logn)=O(n)

==> O(n⁵ + 2^logn)=O(n⁵ + n)=O(n⁵)

What should be the Big O of f(n) = n^5 + 2^log(n)?

2 Answers