Show that n1000000 O1000001n based on the formal definition

Show that n^1000000 = O(1.000001^n) based on the formal definition of big-0 (see below). Defintion [Asymptotic upper bound] We say T(n) = O(f(n)) if there exist constants c greaterthan 0 and n_0 greaterthan 0 such that T(n) lessthanorequalto c f(n) holds for all n greaterthan n_0. It suffices to present the values of c and n0 and explain how you obtained them. A complete proof (i.e., that it holds for all n greaterthanorequalto n_0) is not required.

Solution

1. n^1000000 = O(1.000001ⁿ)
Let us find the breakeven point n₀ . Point where both the functions T(n) and f(n) are equal.
Now when can n^1000000 = 1.000001ⁿ = > Take Log both the sides
1000000 log n₀ = n₀ log 1.000001
=> (log n₀) / n₀ = 1.000001 / 1000000
=> (log n₀) = n₀ *(1.000001 / 1000000)
Take derivatives boith the sides [log n derivative is 1/n and n is 1]
1/ n₀ = (1.000001 / 1000000)
So n₀ = 1000000/1.000001

So Breakeven Point is found i.e At this point both T(n) and f(n) are same.

So Let c be 1000000/1.000000 , decreasing the denominator increases its values and its more than n₀
Hence Now cf(n) >= T(n) for all n>=n₀

n^1000000 = c * (1.000001ⁿ )

where c = 1000000/1.000000 = 1000000     ,

Therefore we can say that n^1000000 = O(1.000001ⁿ) for any n >= n₀      i.e n >= 1000000/1.000001


Hence Proved.

Let me know if there is any concern.