33 lines
602 B
Markdown
33 lines
602 B
Markdown
# 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)$
|
|
|
|
|
|
|