602 B
602 B
Review 4-2
- Hajin Ju, 2024062806
Problem 1
Guess the solution to the recurrence T(n) = T(n/3) + T(2n/3) + cn, where c is constant, is \Theta(n\lg n) by applealing to a recursion tree.
Solution 1
- level 0
\Sigma = cn - level 1
\Sigma = cn/3 + 2cn/3 = cn - level 2
\Sigma = cn/9 + 2cn/9 + 2cn/9 + 4cn/9 = cn - level k
\Sigma = cn - level h
\Sigma = cn
The shortest depth n\to 1 is h = \lg_{3/2}{n}
The longest depth n\to 1 is h = \lg_{3}{n}
so T(n) = \text{depth} * cn and
cn \lg_{3/2}{n} \leq T(n) \leq cn \lg_{3}{n}
therefore T(n) = \Theta(n\lg n)