3
$\begingroup$

Say I have the following recurrence:

$$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$

where $n = 2^k$, $k \in \mathbb{N} $ and $T(1) = 1$.

simplified to:

$$T(n) = n \log_2n + \sum_{i=1}^{\log_2n}T\left(\frac{n}{2^i}\right) $$

The Master's theorem is not applicable; neither is the Akra-Bazzi method since $k = \log_2$ is not a constant.

What strategy can I use to find a closed form solution? I have a feeling that the closed form is $T(n) = \sum_{i=0}^{\log_2n}\left[j\frac{n}{2^i} \log_2 \left(\frac{n}{2^i} \right)\right] + 1 $ where $j = \max\left(1, 2^{i-1}\right)$ but would like a proof.

$\endgroup$
  • $\begingroup$ Is $n$ an integer power of $2$? $\endgroup$ – John Feb 7 '14 at 22:57
  • $\begingroup$ Yes! I fixed this in the question $\endgroup$ – mort Feb 7 '14 at 23:01
  • $\begingroup$ Usually it helps to define $S(n)=\sum_{i=1}^{\log_2n}T\left(\frac n{2^i}\right)$ and use the recursion for $T(n)$ t find an expression for $S(n)$. $\endgroup$ – Ragnar Feb 7 '14 at 23:02
  • $\begingroup$ So $ S(n)= n\log_2n + S(n-1) $ ? $\endgroup$ – mort Feb 7 '14 at 23:05
  • $\begingroup$ Shouldn't the second display equation be $T(n)=n+\dots$? Where did the $\log_2n$ come from? $\endgroup$ – Ross Millikan Feb 8 '14 at 3:33
5
$\begingroup$

Since we only need and evaluate $T(n)$ when $n$ is a power of $2$, say that $a(k)=T(2^k)$. The recursion becomes (I will use $n$ again from now on): $$ a(n)=n2^n+\sum_{i=0}^{n-1}a(i) $$ Define $s(n)=\sum_{i=0}^na(i)$. The above relation can be rewritten to $$ s(n)-s(n-1)=n2^n+s(n-1) $$ thus $$ s(n)=n2^n+2s(n-1) $$ This is is just a first degree linear recurrence relation that should be solvable.

Since we have $T(1)=1$, it follows that $a(0)=1$ and thus $s(0)=1$. The general solution for the recursion relation is $$ s(n)=2^{n-1}(n(n+1)+C) $$ for any constant $C$. (I found this using mathematica. The homogeneous part ($C2^{n-1}$) is obvious, but the inhomogeneous part is (probably) easiest found by writing out some small values. See @CarstenSchultz's comment below for a nice way to find it.) Solving this with $n=0$ gives $$ 1=\frac 12 C $$ Thus, $C=2$ and we get $$ s(n)=2^{n-1}(2+n+n^2)\\ a(n)=s(n)-s(n-1)=2^{n-2}(2+3n+n^2)\\ T(2^n)=s(n)-s(n-1)=2^{n-2}(2+3n+n^2)\\ $$ Note that $a(0)=T(1)=1\neq s(0)-s(-1)=\frac 12$. Since $s(0)=1$, we have $s(-1)=0$, which makes sense since it is an empty sum. The formula for $s(n)$ is thus only valid for nonnegative $n$.

$\endgroup$
  • $\begingroup$ Actually, $T(1) = 1$. I will add this to my question $\endgroup$ – mort Feb 7 '14 at 23:08
  • $\begingroup$ Regarding the part, where you used Mathematica: The recursion can be rewritten as $\frac{s(n)}{2^n}=n+\frac{s(n-1)}{2^{n-1}}$, and hence $\frac{s(n)}{2^n}=\sum_{k=1}^n k+K=\binom {n+1}2+K$. $\endgroup$ – Carsten S Feb 7 '14 at 23:42
  • $\begingroup$ @CarstenSchultz, Clever trick to make another substitution. I was t0o lazy to think myself, but I should have thought of that. $\endgroup$ – Ragnar Feb 7 '14 at 23:44
  • $\begingroup$ Nothing wrong with using Mathematica. $\endgroup$ – Carsten S Feb 7 '14 at 23:45
  • $\begingroup$ Shouldn't that be $a(n)=2^n+\dots$? in the first display equation? OP's second equation has a $\log_2 n$ that would justify your $n$ $\endgroup$ – Ross Millikan Feb 8 '14 at 3:34
2
$\begingroup$

As an additional comment on this, note that if we define $T(n)$ for all $n$ and not just powers of two with $T(0)=0$ and $T(1)=1$ like this $$T(n) = \sum_{k=1}^{\lfloor \log_2 n \rfloor} T(\lfloor n/2^k \rfloor) + n \lfloor \log_2 n \rfloor,$$ and the binary representation of $n$ is given by $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ then the exact formula for all $n$ where $n\ge 2$ is $$T(n) = 2^{\lfloor \log_2 n \rfloor - 1} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) [z^j] \frac{1-z}{1-2z} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}$$ because $$\frac{1}{1-z-z^2-z^3-\cdots} = \frac{1-z}{1-2z}.$$ This simplifies to $$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \sum_{j=1}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) [z^j] \frac{1-z}{1-2z} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}$$ Now note that for $j\ge 1$ $$[z^j] \frac{1-z}{1-2z} = 2^{j-1}$$ so this in turn again simplifies, this time to $$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \sum_{j=1}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) 2^{j-1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}$$ which is $$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Now for an upper bound consider a string of one digits giving $$T(n)\le 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) (2^{\lfloor \log_2 n \rfloor+1}-2^j) \\= 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \frac{1}{2} (\lfloor \log_2 n \rfloor +1) \left(\lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} - 2^{\lfloor \log_2 n \rfloor+1} + 2\right).$$ For a lower bound consider a one digit followed by zeros giving $$T(n)\ge 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor -j ) 2^{\lfloor \log_2 n \rfloor} \\ = 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n + \frac{1}{4} \lfloor \log_2 n \rfloor(\lfloor \log_2 n \rfloor - 1) 2^{\lfloor \log_2 n \rfloor}.$$

The upper and lower bounds are attained and cannot be improved upon.

Selecting the dominant terms from the two bounds we finally get a complexity of $$\Theta\left((\lfloor \log_2 n \rfloor)^2\times 2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left((\log_2 n)^2 2^{\log_2 n}\right) = \Theta\left(n \times (\log_2 n)^2\right).$$

A similar calculation was done at this MSE link.

Addendum. The sequence of values of $T(2^j)$ using our definition is $$3, 12, 40, 120, 336, 896, 2304, 5760, 14080, 33792,\ldots$$ which agrees (as it ought to) with the formula found by @Ragnar $$T(2^j) = 2^{j-2}\times(2+3j+j^2).$$ (This is just a re-write of our lower bound, which to give credit was posted second.)

Remark as of Sat Feb 8 20:37:05 CET 2014. The upper limit of the outer sum can be replaced by $\lfloor \log_2 n\rfloor-1$ but the formulas are correct as stated.

$\endgroup$
1
$\begingroup$

I'd just start with $T(1)$ and look for a pattern:

$$T(2^1) = 1 \cdot 2^1 + 2^{1-1}T(1)$$ $$T(2^2) = 2\cdot 2^2 + 1\cdot 2^1 + (2^{2-1}) T(1)$$ $$T(2^3) = 3\cdot 2^3 + 2\cdot 2^2 + 2 \cdot 1 \cdot 2^1 + 2^{3-1} T(1)$$ $$T(2^4) = 4\cdot 2^4 + 3\cdot 2^3 + 2 \cdot 2 \cdot 2^2 + 4 \cdot 1 \cdot 2^1 + 2^{4-1} T(1)$$

so that if $T(1) = 1$,

$$T(2^n) = 2^{n-1} + \sum_{k=1}^n k \cdot 2^k + \sum_{k=1}^{n-2} (2^{n-k-1}-1)2^k.$$

$\endgroup$
  • $\begingroup$ This can not be true. $T(16) = 120$, but your solution gives 106. $\endgroup$ – mort Feb 7 '14 at 23:16
  • $\begingroup$ You're right. I didn't carry it out far enough. Edited my answer. $\endgroup$ – John Feb 7 '14 at 23:43

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.