I am attempting to solve the above recurence by giving tight $\Theta$ bounds.
Assume that the logs here are all base 2!
To solve a recursion tree as far as I understand, I need two things.
- The height of the tree
- Work or Computation per level of the tree
The product of these 1. and 2. will tell me how the recurrence scales.
As for part 1.)
I was able to gauge that $n^\frac{1}{2h} = 2$ where an input with size 2 is my base case, and $h$ is the height of the tree.
Then, $h \approx \frac{log_2(n)}{2}$
I have issues with finding the work per level of the tree however, since this value changes depending which level of the tree you are on. I come to find that it is $n^\frac{1}{2i}10n^\frac{1}{2i}$
Where $i$ is the level of the tree you are looking at.
However, how do I use this information to solve the recurrence?