5. Using the definition of Big- notation, show that the runtime T(n)3n3 +2n lg(n

Question

5. Using the definition of Big- notation, show that the runtime T(n)3n3 +2n lg(n) is e (n3). Hint: look at how it is done for Big-0, and do the same for 2. 6. In book (Chap 1) we saw the theorem: T n(n+)(2n+1) With induction, prove that this theorem is true for any natural number 2 1. Hint: Establish base case, then assume true for k, prove for k+1

Explanation / Answer

5. 3n3+2n+lg(n) = 4 and n >= 2 So, T(n) = O(n3) 6. Case n = 1 ---------- LHS = 1 RHS = 1(1+1)(2+1)/6 = 1 Case n = k+1 ------------ LHS = 1^2 + 2^2 + 3^2 + ........ + (k^2) + (k+1)^2 = (k)(k+1)(2k+1)/6 + (k+1)^2 = (k)(k+1)(2k+1)/6 + (k+1)^2 = (k+1)(k+2)(2k+3) / 6 RHS = (k+1)(k+1+1)(2(k+1)+1)/6 = (k+1)(k+2)(2k+3) / 6 So, LHS = RHS Hence proved

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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