Solve the recurrence equation shown below, andexpress T(n) as a function of n. I

Question

Solve the recurrence equation shown below, andexpress T(n) as a function of n. It is all right to assume n is apower of 2.

T(n) = T(n/2) + n2 for n > 2
T(1) = 0

Explanation / Answer

Assumption: N is a power of 2...therefore N= 2k for somek>= 1 T(N) = T(N/2) +N2           = T(2k-1 )+ 22k   [by replacing N= 2k]           = T(2k-2 )+ 22k-2 + 22k           =T(2k-3) +22k-4 + 22k-2 + 22k         It will go on till we getT(1) T(N) = T(1) + 1 + 22 +...............+ 22k-2+22k           = 0 +4+42 +................+4k-1 +4k           = 4 * (4k-1)/3           = 4* (N2-1)/3 Therefore T(N) = (N2 -1)*(4/3)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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