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.

  • 1
    $\begingroup$ Take a look at math.stackexchange.com/questions/506489/… $\endgroup$ – marty cohen Nov 10 '13 at 2:55
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – 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.


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.