solve the recurrence equations using master method
1) T(n) = 8T(n/3) + 2^n c
Answers
Answer:
Solving Recurrences with the Iteration/Recursion-tree Method
• In the iteration method we iteratively “unfold” the recurrence until we “see the pattern”.
• The iteration method does not require making a good guess like the substitution method (but
it is often more involved than using induction).
• Example: Solve T(n) = 8T(n/2) + n
2
(T(1) = 1)
T(n) = n
2 + 8T(n/2)
= n
2 + 8(8T(
n
2
2
) + (n
2
)
2
)
= n
2 + 82T(
n
2
2
) + 8(n
2
4
))
= n
2 + 2n
2 + 82T(
n
2
2
)
= n
2 + 2n
2 + 82
(8T(
n
2
3
) + ( n
2
2
)
2
)
= n
2 + 2n
2 + 83T(
n
2
3
) + 82
(
n
2
4
2
))
= n
2 + 2n
2 + 22n
2 + 83T(
n
2
3
)
= . . .
= n
2 + 2n
2 + 22n
2 + 23n
2 + 24n
2 + . . .
– Recursion depth: How long (how many iterations) it takes until the subproblem has
constant size? i times where n
2
i = 1 ⇒ i = log n
– What is the last term? 8iT(1) = 8log n
T(n) = n
2 + 2n
2 + 22n
2 + 23n
2 + 24n
2 + . . . + 2log n−1n
2 + 8log n
=
log
Xn−1
k=0
2
kn
2 + 8log n
= n
2
log
Xn−1
k=0
2
k + (23
)
log n
• Now Plog n−1
k=0 2
k
is a geometric sum so we have Plog n−1
k=0 2
k = Θ(2log n−1
) = Θ(n)
• (23
)
log n = (2log n
)
3 = n
3
T(n) = n
2
· Θ(n) + n
3
= Θ(n
3
)