# 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)$