Time Complexity

Question

f(n)= n^0.0000001

g(n)=lg n(base 2)

Is g(n)=O(f(n))...?

For the large values of n

n= 10^8   f(n)= 1.0000018 , g(n)=26.565

n=10^10  f(n)=1.0000023,   g(n)=33.21

So I am getting f(n)=O(g(n))...

Can anyone please explain why g(n)=O(f(n))....?

Answer 1

There is no limit on a large value being considered. 

f(n)= n^0.0000001 = n^(10^-7)
g(n)=lg n(base 2)

n= 10^8   f(n)= 1.000001842 , g(n)=26.565

Now, I take n = 10^(10^8)

f(n) = n^(10^-7) = (10^(10^8))^(10^-7) = 10^(10^(8-7)) = 10^10
g(n) = 10^8 log₁₀ 2

So, f(n) becomes larger. Thus for any x, we can have an n, where n^x becomes larger than log n and stays larger from there on wards for any higher n. 

Comments

Why on n= 10^(10^8) , f(n)=10^10?

---

Added that step :)

---

But how could we identify that  n^.0000001 is exponential.. as exponential is of form a^x where a is a constant?

---

Sorry. that's right n^0.00000001 is not exponential an exponential function. For exponential function, the base should be constant. Here, its the other way around.

What I meant is n raised to any positive number (even less than 1) is asymptotically larger than log n.