Just pick arbitrary c and n0 can make it works Show that n10

Just pick arbitrary c and n0 can make it works.

Show that n^1000000 = O(1.000001^n) based on the formal definition of big-O (see below). Defintion [Asymptotic upper bound] We say T(n) = O(f(n)) if there exist constants c > 0 and n_0 greaterthanorequalto 0 such that T(n) lessthanorequalto c f(n) holds for all n greaterthanorequalto 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

Answer:

Answer:

We know by Big O definition :

T(n) <= c x O(f(n)) -----(1)

let c = 1

Here T(n) = n^1000000 , f(n) = 1.000001^n

n^1000000 < = 1 x 1.000001^n

Now apply in equation (1) , we get

n^1000000 <= 1.000001^n

Apply log on both sides , we get

log(n^1000000) < = log(1.000001^n)

1000000 x log n < = nlog (1.000001)

Now substitute the value of n and check the condition , right hand side will be greater always ( take any value of n0 bigger value of n will give more appropriate result).

Hence n^1000000 = O(1.000001^n)

Now in order to check at what value of n0 T(n) = O(f(n)) , lets equate the both : -

1000000 xlogn = n

=> 1000000 x logn - n = 0

=> logn - n = 0

n = 1.5