Three Children Per Node

Here is the recursion tree for $T(n) = 3T(n/2) + n$ with $T(1) = 1$ , evaluated at $n = 2^{20}$ :

level	nodes	work per node	level total
0	1	1,048,576	$1.05 \times 10^6$
1	3	524,288	$1.57 \times 10^6$
2	9	262,144	$2.36 \times 10^6$
...	...	...	...
20	$3^{20}$	1	$3.49 \times 10^9$

What closed form does this tree give?

$\Theta(n^2)$

$\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$

$\Theta(n \log n)$

$\Theta(n^{1.5})$