# find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

Find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$, $\ T(n)=c$.

I didn't manage to find a tight upper bound. With rough evaluations i got $O(n^{logk})$ by $T(n) < n+kT(\frac n 2)$

Also tried the following:

$T(n) = n+T(\frac{n}{2})+...+T(\frac{n}{2^{k}})$

$= n+\sum_{i_{1}=1}^{k}\frac{n}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}T(\frac{n}{2^{i_{1}+i_{2}}})$

$\vdots$

$\leq n+\sum_{i_{1}=1}^{k}\frac{n}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}\frac{n}{2^{i_{1}+i_{2}}}+...+\sum_{i_{1},i_{2},...,i_{log(n)}=1}^{k}\frac{n}{2^{\sum_{j=1}^{log(n)}i_{j}}}$

$= n\left(1+\sum_{i_{1}=1}^{k}\frac{1}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}\frac{1}{2^{i_{1}+i_{2}}}+...+\sum_{i_{1},i_{2},...,i_{log(n)}=1}^{k}\frac{1}{2^{\left(\sum_{j=1}^{log(n)}i_{j}\right)}}\right)$

But i do not know how to continue from here.

Another attempt was changing variables: $2^m=n$ and $U(m)=T(2^m)$ then $U(m)= 2^m+U(m-1) +...+U(m-k)$ but i did not manage to get any progress on that direction either.

Any help will be appreciated, thanks.

• Take a look at math.stackexchange.com/questions/506489/… – marty cohen Nov 10 '13 at 2:55
• Just for the record and since the OP is still on the site, I fail to understand how the accepted post, competently explaining some relevant heuristics, was considered as answering the question. – Did Mar 12 '16 at 10:50

Seems like if you guess that $T(n)\sim \alpha n$, then you have $$\alpha n \sim n +\alpha\left(\frac{n}{2}+\frac{n}{4}+\ldots+\frac{n}{2^k}\right)=n\left(1+\alpha\left(1-\frac{1}{2^k}\right)\right),$$ which is consistent provided that $\alpha=2^k$. For any fixed $k$, this will be the large-$n$ behavior (regardless of $c$, which only affects the small-$n$ behavior).

This can be done with the Akra-Bazzi method. Using Wikipedia's notation, the setup is

\begin{eqnarray*} a_i \equiv 1 \\ b_i = 2^{-i} \\ h_i(x) \equiv 0 \\ g(x) = x \\ \end{eqnarray*}

The next step would be to solve

$$f(p) \equiv \sum_{i=1}^k 2^{-ip} = 1$$

for $p$. But in this particular case we don't need to know what $p$ is. All we need to know is that $p \in (0,1)$, which you can check with the intermediate value theorem, noting that $f(0)=k>1$ and $f(1)=\sum_{i=1}^k 2^{-i} = 1-2^{-k} < 1$. So given such a $p$ the Akra-Bazzi method would say that

$$T(x) = \Theta \left ( x^p \left ( 1 + \int_1^x \frac{u}{u^{p+1}} du \right ) \right ) \\ = \Theta \left ( x^p \left ( 1 + \Theta \left ( x^{-p+1} \right ) \right ) \right ) \\ = \Theta(x)$$

This is a special case of a previous problem I proposed and partially solved:

If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor)$, show that $T(n) = \Theta(n)$

My solution there does show that $T(n) = \Theta(n)$ and conjectures that $\dfrac{T(n)}{n} \to 2^k$.

• This conjecture holds for the upper bound that I calculated above because for a string of one digits $\lfloor\log_2 n\rfloor+1$ is asymptotically $\log_2 n$. This also agrees with the accepted definitive answer. – Marko Riedel Jul 28 '14 at 3:14

We can solve another closely related recurrence that admits an exact solution and makes it possible to get precise bounds. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = n + \sum_{q=1}^p T(\lfloor n/2^q \rfloor).$$

Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\sum_{q=1}^p z^q} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$ This follows more or less by inspection.

Now to get an upper bound consider a string of one digits which yields $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\sum_{q=1}^p z^q} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\= \sum_{j=0}^{\lfloor \log_2 n \rfloor} (2^{\lfloor \log_2 n \rfloor+1-j}-1) [z^j] \frac{1}{1-\sum_{q=1}^p z^q} \\= 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q} - \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\sum_{q=1}^p z^q}.$$

Note that this bound is attained and cannot be improved. Since $(1/2)^j \le 1$ it is upper bounded by $$(2^{\lfloor \log_2 n \rfloor+1} - 1) \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q} \\ \le (2^{\lfloor \log_2 n \rfloor+1} - 1) \sum_{j=0}^\infty \left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q} \\= (2^{\lfloor \log_2 n \rfloor+1} - 1) \frac{1}{1-\sum_{q=1}^p (1/2)^q} \\= 2^p (2^{\lfloor \log_2 n \rfloor+1} - 1).$$

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\sum_{q=1}^p z^q} 2^{\lfloor \log_2 n \rfloor-j} \\= 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}.$$

At this point unfortunately we cannot avoid studying the roots of $$f(z) = 1-\sum_{q=1}^p z^q.$$ We need the root $\rho$ that is closest to the origin and more precisely, we have to show that $\rho > 1/2.$ Since $f(0) = 1$ and $f(1) = - (p-1)$ we have at least one root $\rho$ in $(0, 1)$ and by the sign and the continuity of $f'(z)$ it is the only one. We must have $\rho > 1/2$ since otherwise $\sum_{q=1}^p z^q < 1$ because $p$ is finite. Furthermore there are no complex roots with modulus $\rho$ because by the triangle inequality there would be cancellation and we would again have $|\sum_{q=1}^p z^q| < 1.$ This last argument also applies to the negative real negative root that appears when $p$ is even.

The conclusion is that $\rho$ is the dominant singularity and $$[z^j] \frac{1}{1-\sum_{q=1}^p z^q} \sim -\frac{1}{\rho} \mathrm{Res}(1/f(z); z=\rho) \times \rho^{-j} \\= \frac{1}{\sum_{q=1}^p q\times \rho^{q-1}} \times \rho^{-(j+1)} = \frac{1}{\sum_{q=1}^p q\times \rho^q} \times \rho^{-j}.$$ Here we have used the fact that $$\frac{1}{z-\rho} = - \frac{1}{\rho} \frac{1}{1-z/\rho}.$$ We have shown that $$\sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q} \sim \frac{1}{\sum_{q=1}^p q\times \rho^q} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2\rho} \right)^j.$$

Now use the fact that $\rho > 1/2$ to get $1 > 1/2/\rho$ to obtain (geometric series) that this sum is bounded above by a constant that does not depend on $n.$

We are now ready to conclude. We have established that

• $T(n)$ is upper bounded by $2^p (2^{\lfloor \log_2 n \rfloor+1} - 1)$
• $T(n)$ is lower bounded by a multiple of $2^{\lfloor \log_2 n \rfloor}$ times a coefficient from an interval that does not depend on $n.$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#006}{2^{\lfloor \log_2 n \rfloor} \in \Theta\left(2^{\log_2 n}\right) = \Theta\left(n\right)}.$$

These are both in agreement with what the Master theorem would produce.

Remarks. This MSE link I and this MSE link II present closely related arguments. The calculation of the upper bound uses an annihilated coefficient extractor which is also used at this MSE link III.