So, please focus on finding the values of C and n0 and explain how you have foun

Question

So, please focus on finding the values of C and n0 and explain how you have found them. Figure out how large n0 has to be to satisfy the big-O condition. Making a case based on the observation instead of analytical reasoning is good enough. The objective of this exercise is to actually see a case, show arbitrary constants c and n0 that satisfy the big-Oh condition.

2. (25 points) Show that 1000000 O(1.000001m) based on the formal definition of big-O (see n below). Defintion [Asymptotic upper boundl We say TOn-O(f(n)) if there exist constants c >0 and no 20 such that T(n) S c f(n) holds for all n no. It suffices to present the values of c and no and explain how you obtained them. A complete proof (i.e., that it holds for all n 2 no) is not required.

Explanation / 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)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.