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?

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