Analyze, using therecursion tree method, the rate of growth of a T(n) that satis

Question

Analyze, using therecursion tree method, the rate of growth of a
T(n) that satisfies the following recurrence:

T(1) = c, and if n > 1 then T(n) = 8T(n/3) + cn2where c is a constant.
This is just about the “asymptotic order” of thesolution, not its exact value. You can
assume, for simplicity, that n = 3q for someinteger q Analyze, using therecursion tree method, the rate of growth of a
T(n) that satisfies the following recurrence:

T(1) = c, and if n > 1 then T(n) = 8T(n/3) + cn2where c is a constant.
This is just about the “asymptotic order” of thesolution, not its exact value. You can
assume, for simplicity, that n = 3q for someinteger q

Explanation / Answer

Applying master’stheorem
Here   a =8 b =3 so log ba =  log 3 8 other power=2    (from cn2) which is > log 3 8    [ reasonlog 3 8< (log 3 9 = 2)] so the order willbe = O(n 2)

//Hope this will help you now..

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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