2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Hint, suppose $n=2^k$ for some natural number $k$. Can you simplify the total sum? $\endgroup$
    – John L.
    Apr 16, 2022 at 0:26
  • $\begingroup$ 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$ $\endgroup$
    – Rodrigo
    Apr 16, 2022 at 9:33
  • $\begingroup$ 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? $\endgroup$
    – Rodrigo
    Apr 16, 2022 at 9:44

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$) ? $\endgroup$
    – Rodrigo
    Apr 18, 2022 at 9:41
  • $\begingroup$ @roto, please come to this chat room for a chat. $\endgroup$
    – John L.
    Apr 18, 2022 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.