3
$\begingroup$

I have a recurrence relation which is like the following:

$T(n) = 2T(\frac{n}{2}) + \log_{2}n$

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?

$\endgroup$
2
$\begingroup$

This looks like the running time of a divide-and-conquer algorithm. You can apply the Akra-Bazzi method here. The method works for recurrences of the form:

$$T(n)=\sum_i^k a_iT(b_i n+h_i(n))+g(n), \forall n\ge n_0$$

In your case:

$k=1$

$g(n)=\log n$

$a=2,b=1/2$

$h(n)=0$

For this to work, we have to find a number $p$ satisfying $ab^p=1$. That's easy,let $p=1$.

The method tells us that $T(n)=\Theta(n^p(1+\int_1^n\frac{g(x)}{x^{p+1}}dx))$

I computed the integral on WolframAlpha. The answer is $1-\frac{\log n + 1}{n}$.

Therefore, $$T(n)=\Theta(2n-\log n)=\Theta(n)$$


Here is another way of solving this. Let $n=2^m$

$T(2^m)=2(2T(2^{m-1})+(m-1))+m=2^2T(2^{m-2})+m+(m-1)=\dots=2^kT(2^{m-k})+m+(m-1)+\dots+m-k+1=2^m\Theta(1)+m(m-1)/2=\Theta(2^m)$.

So $T(n)=\Theta(n)$

$\endgroup$
  • 1
    $\begingroup$ Master Theorem applies here and is easier than Akra-Bazzi. Plus if you're willing to use Wolfram Alpha you can get the recurrence solution directly. $\endgroup$ – SamM Mar 7 '13 at 20:15
  • 1
    $\begingroup$ The first half makes it harder than it has to be, but +1 for the second half. $\endgroup$ – Joe Mar 8 '13 at 3:45
  • $\begingroup$ @SamM The point is to expose the Akra-Bazzi method. $\endgroup$ – saadtaame Mar 8 '13 at 11:37
  • $\begingroup$ @Joe Thanks! Change the order if that makes more sense to you :D $\endgroup$ – saadtaame Mar 8 '13 at 12:23
2
$\begingroup$

For $\sum_{0 \le r \le k} r \cdot 2^r$, start with: $$ \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r $$ As this is a polynomial, the following mangling doesn't need any justification: $$ z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r $$ Doing the operations indicated: $$ \sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2} $$ Finally: $$ \sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n) $$

$\endgroup$
  • $\begingroup$ This answer is incorrect; it is $\Theta(n)$. $\endgroup$ – SamM Mar 7 '13 at 20:17
  • 2
    $\begingroup$ @SamM, Impossible, just the last term is $\Theta(k 2^k) = \Theta(n \log n)$. $\endgroup$ – vonbrand Mar 7 '13 at 20:26
  • $\begingroup$ Ah, I take it back. You were solving for the term he was subtracting from the original equation, not the recurrence itself. If you substitute back in you get $T(n) = \Theta(n)$. $\endgroup$ – SamM Mar 7 '13 at 20:31

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.