How to tackle a recurrence that contains the sum of all previous elements?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.