Trying to understand the basic about recurrence trees

Question

I have little background on recurrence trees, and I am working on the following exercise:

Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we conclude complexity-wise?

My attempt. For $n=2$ we have the following recurrence tree:

Recursive Call Recurrence Tree Sum
 
 T(2) 3log(2) 3log(2)
 / \
 T(1) 3log(1) 3log(1) 6log(1) = 0

Since we arrived at $T(1)$, we should stop (IS THIS TRUE?) with our tree and the total sum is given by 3ドル\log(2) + 0 = 3\log(2) = \Theta(1)$ which means that, complexity-wise, for $T(2)$, we're dealing with constant-time complexity.

For $n=4$, and using the same method, we could should that the sum would be 3ドル\log(4) + 6\log(2) = \log(4^3*2^6) = \Theta(1)$.

Let's upgrade the exercise and draw the recurrence tree for any $n$. Here follows my attempt:

 Recursive Call Recurrence Tree Sum
 
 T(n) 3log(n) 3log(n)
 / \
 T(n/2) 3log(n/2) 3log(n/2) 6log(n/2)
 / \
 / \
 T(n/2^2) 3log(n/4) 3log(n/4) (...) 12log(n/4)
 (...) 
 
 T(n/2^i) (...) 3*2^i log(n/2^i)

And we stop when $\frac n {2^i} = 1 \Leftrightarrow \lg n = i$, where $\lg n = \log_2 (n)$. With this being said, our total sum is $\sum_{i=0}^{\lg n} \left(3*2^i \log(\frac n {2^i} ) \right) $. And I don't know how to proceed from here.

Is my attempt wrong at any point?

• 喜欢算法和数学: Hint, suppose $n=2^k$ for some natural number $k$. Can you simplify the total sum?
• Rodrigo: Taking your hint, we would have that the total sum would be $\sum_{i=0}^{lg 2^k = k} 3*2^i \log(\frac{2^k}{2^i}) = \sum_{i=0}^{k} 3*2^i \log(2^{k-i}) = 3\log(2)\sum_{i=0}^{k} (k-i)2^i = 3k\log(2)\sum_{i=0}^{k} 2^i - 3\log(2) \sum_{i=0}^{k} i2^i$
• Rodrigo: I could simplify the sums, and I did so on paper, but I think that didn't help much. Is the attempt I did for the cases $n=2$ and $n=4$ well done?

Answer 1

"Since we arrived at $T(1)$, we should stop."

Yes, the recurrence relation should not be applied any more once the initial conditions are reached.

It should not be a problem to assume the value of $T(1)$ and no others are given as the initial conditions for the recurrence relation, although it does not violate any rules if all values of $T(1), T(2), T(3), T(4)$ are given independently along with the recurrence relation $T(n) = 2T(n/2) + 3\log(n)$, making the task of drawing the recurrence trees for $n=2$ and $n=4$ vacuous.

Assume that $T(1)=t_1\ge0$. Assume the $\log$ in the question is the logarithm with base 2ドル$. A difference base will not affect the result of asymptotic analysis as long as it is a constant greater than 1.

$T(2)=2T(1) + 3\log_2(2) = 2t_1 + 3.$ Note $t_1$ should appear.
$T(4)=2T(2) + 3\log_2(4) = 4t_1 + 12.$

So it takes up to some constant time to compute $T(2)$ and $T(4)$, both of which are constants, too.

"3ドル\log(2) + 0 = 3\log(2) = \Theta(1)$" might not be outright wrong. However, "$=\Theta(1)$" makes sense only when the left-hand side is viewed as a function of a variable that could go to infinity.

Obtain an asymptotic approximation for $T(n)$

The recursion trees for $n=2$, $n=4$ and general $n$ in the question are pretty good.

Suppose $n=2^k$ for some integer $k>0$. Do not forget $t_1$.

$$T(n)=2^kt_1 + \sum_{i=0}^{\log_2(2^k)} 3\cdot2^i \log_2(\frac{2^k}{2^i}) = 2^kt_1 + \sum_{i=0}^{k} 3\cdot2^i (k-i)= 2^kt_1 + 3\sum_{i=0}^{k-1}2^i (k-i)$$

Intuitively, the sum $\sum_{i=0}^{k-1}2^i (k-i)$ is not much different from 2ドル^{k-1}$, the last term where $i=k-1$.

• "Intuitively" is meant to alert you to learn this kind of approximate reasoning/understanding.
• "not much different" means "different by at most a constant factor". This factor might be as large as 999999999ドル$ or even much larger. As long as it is independent of $n$, it does not matter how large it is.
• Look at all the summands, $\cdots,\ 2^{k-4}4,\ 2^{k-3}3,\ 2^{k-2}2,\ 2^{k-1}1$, from the back to the front. Each summand is a product of a power of 2ドル$ and another number. The power of 2ドル$ shrinks to one half each time and the other number increases by 1ドル$ each time. The shrinkage of the power of 2ドル$ is so much more significant than the addition of 1ドル$, the product shrinks very fast as well. It shrinks so fast that sum of all them is not much different from the first term (from the back).

Let us realize the intuition above by accurate computations.

Let $X=\sum_{i=0}^{k-1}2^i (k-i)$. $$\begin{aligned} X&=-X+2X\\ &=-(k + 2(k-1) + 2^2(k-2) + 2^3(k-3) + \cdots + 2^{k-2}2 + 2^{k-1})\\ &\quad\quad\quad +(2k\quad\quad\ + 2^2(k-1) + 2^3(k-2) + \cdots + 2^{k-2}3 + 2^{k-1}2 + 2^{k}) \\ &\quad\text{(combine terms with the same power of 2)}\\ &=(2^k-k)+\sum_{i=1}^{k-1}2^i \\ &=2^{k}-k+(2^k-2) \quad\quad(\text{which is not much different from }2^{k-1}) \end{aligned}$$ So, $T(n)=2^kt_1+3X =2^k(t_1+6)-3k-6=n(t_1+6)-3\log_2(n)-6=\Theta(n)$.

• Rodrigo: I am sorry, I don't understand where 2ドル^k t_1$ comes from in the $T(n)$ deduction. I understand it is related to us getting to the base case $T(1),ドル but why does it origin 2ドル^k t_1$ ? (I.e., how do you find the constant that multiplies by $t_1$ in the general formula for $T(n)$) ?
• 喜欢算法和数学: @roto, please come to this chat room for a chat.