Scribd
Upload
69 views1 page

Recursion Tree Solution

The document describes using a recursion tree to determine the asymptotic upper bound of T(n) = 4T(n/2 + 2) + n. The recursion tree has O(log n) levels and Θ(n^2) leaves. Summing the costs at each level gives an overall cost of Θ(n^2). The substitution method verifies this upper bound.

Uploaded by

Zubair Rizwan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
69 views1 page

Recursion Tree Solution

The document describes using a recursion tree to determine the asymptotic upper bound of T(n) = 4T(n/2 + 2) + n. The recursion tree has O(log n) levels and Θ(n^2) leaves. Summing the costs at each level gives an overall cost of Θ(n^2). The substitution method verifies this upper bound.

Uploaded by

Zubair Rizwan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Recursion tree solution

Use a recursion tree to determine a good asymptotic upper bound on the


recurrence T(n) = 4T(n / 2 + 2) + nT(n)=4T(n/2+2)+n. Use the substitution
method to verify your answer.

 The subproblem size for a node at depth ii is n / 2^in/2i.


Thus, the tree has \lg n + 1lgn+1 levels and 4^{\lg n} =
n^24lgn=n2 leaves.
The total cost over all nodes at depth ii, for i = 0, 1, 2, \ldots, \lg n -
1i=0,1,2,…,lgn−1, is 4^i(n / 2^i + 2) = 2^i n + 2 \cdot
4^i4i(n/2i+2)=2in+2⋅4i.
\begin{aligned} T(n) & = \sum_{i = 0}^{\lg n - 1} (2^i n + 2 \cdot 4^i)
+ \Theta(n^2) \\ & = \sum_{i = 0}^{\lg n - 1} 2^i n + \sum_{i =
0}^{\lg n - 1} 2 \cdot 4^i + \Theta(n^2) \\ & = \frac{2^{\lg n} - 1}{2 -
1}n + 2 \cdot \frac{4^{\lg n} - 1}{4 - 1} + \Theta(n^2) \\ & = (2^{\lg
n} - 1)n + \frac{2}{3} (4^{\lg n} - 1) + \Theta(n^2) \\ & = (n - 1)n +
\frac{2}{3}(n^2 - 1) + \Theta(n^2) \\ & = \Theta(n^2).
\end{aligned}T(n)=i=0∑lgn−1(2in+2⋅4i)+Θ(n2)=i=0∑lgn−12in+i=0∑lgn−1
2⋅4i+Θ(n2)=2−12lgn−1n+2⋅4−14lgn−1+Θ(n2)=(2lgn−1)n+32
(4lgn−1)+Θ(n2)=(n−1)n+32(n2−1)+Θ(n2)=Θ(n2).
 We guess T(n) \le c(n^2 - dn)T(n)≤c(n2−dn),
\begin{aligned} T(n) & = 4T(n / 2 + 2) + n \\ & \
le 4c[(n / 2 + 2)^2 - d(n / 2 + 2)] + n \\ & = 4c(n^2 / 4 + 2n + 4 - dn / 2 -
2d) + n \\ & = cn^2 + 8cn + 16c - 2cdn - 8cd + n \\ & = cn^2 - cdn +
8cn + 16c - cdn - 8cd + n \\ & = c(n^2 - dn) - (cd - 8c - 1)n - (d - 2)
\cdot 8c \\ & \le c(n^2 - dn), \end{aligned}T(n)
=4T(n/2+2)+n≤4c[(n/2+2)2−d(n/2+2)]+n=4c(n2/4+2n+4−dn/2−2d)+n=
cn2+8cn+16c−2cdn−8cd+n=cn2−cdn+8cn+16c−cdn−8cd+n=c(n2−dn)−
(cd−8c−1)n−(d−2)⋅8c≤c(n2−dn),
where the last step holds for cd - 8c - 1 \ge 0cd−8c−1≥0

You might also like