The recursive relation is $T(n)=T(cn)+T((1-c)n)+1$, with $0<c<1$.

I used tree traversal but couldn't find tighter bounds than

$$\text{if }\ c\geq 1 - c\ \text{ then }\\T(n)= O\left ( n^{\frac{1}{log_{\frac{1}{c}}2}} \right)\ \text{ and } \ T(n)= \Omega \left ( n^{\frac{1}{log_{\frac{1}{1-c}}2}} \right)$$

Is it possible to find a tighter bound that this?
A bound which is independent of c?


Edit: the answer below is technically correct, but also stupid, because $k^*$ satisfies $c^{k^*} + (1-c)^{k^*} = 1$ exactly when $k^*=1$.

So in fact I only sort of proved that $T(n)$ is linear, and didn't do a very good job of that, either.

Intuitively, we can say that $T(n)$ should grow kinda sorta like $n^{k^*}$, where $k^*$ satisfies $c^{k^*} + (1-c)^{k^*} = 1$, just by substituting $n^{k^*}$ into the recurrence relation: we want $$n^{k^*} = c^{k^*}n^{k^*} + (1-c)^{k^*}n^{k^*} + 1,$$ or $c^{k^*} + (1-c)^{k^*} = 1$ if we ignore the $+1$ at the end.

We can make this precise. Suppose that $T(n) = \Omega(n^k)$ for some $k < k^*$, which means $c^k + (1-c)^k > 1$. We know that there are $C_0$ and $n_)$ such that $T(n) \ge C_0 n^k$ when $n\ge n_0$. Therefore, for all $n$ such that $cn \ge n_0$ (I assume that $c \le 1-c$), we have $$T(n) \ge T(cn) + T((1-c)n) \ge C_0 (c^k + (1-c)^k)n^k$$ and by iterating this argument, for all $n$ such that $c^t n \ge n_0$, we have $$T(n) \ge C_0 (c^k + (1-c)^k)^t n^k.$$ We can choose $t = \log_{1/c} \frac{n}{n_0}$, and have this argument work, which gives us $$T(n) \ge C_0 (c^k + (1-c)^k)^{\log_{1/c}(n/n_0)} n^k = \Omega(n^{k+\epsilon})$$ where $\epsilon = \frac{1}{\log_{c^k + (1-c)^k} \frac1c} > 0$.

In other words, for all $k < k^*$, if $T(n) = \Omega(n^k)$, then $T(n) = \Omega(n^{k+\epsilon})$. An identical proof shows that for all $k > k^*$, if $T(n) = O(n^k)$, then $T(n) = O(n^{k-\epsilon})$.

This is not quite enough to say that $T(n) = \Theta(n^{k^*})$. In fact, just because $T(n)$ is bounded above and below by polynomials doesn't mean that there's any value of $k^*$ that makes this true: just as an example, we could have $T(n) = \Theta(n^{k^*}\log n)$. However, we do know that there is going to be some value of $k$ such that $T(n) = \Omega(n^{k-\epsilon})$ and $T(n) = O(n^{k+\epsilon})$ for all $\epsilon>0$, and the argument above shows that the only value of $k$ that can be is $k^*$.

  • $\begingroup$ Thank you so much for your time Misha! $\endgroup$ – Evyatar Mar 24 '17 at 17:15
  • $\begingroup$ It also means that the answer given here math.stackexchange.com/questions/723596/tn-tcn-t1-cn1-while-0c1 is incorrect right? I couldn't quite understand the accepted answer there $\endgroup$ – Evyatar Mar 24 '17 at 17:22
  • $\begingroup$ Wait, I'm really stupid. $\endgroup$ – Misha Lavrov Mar 24 '17 at 19:03
  • $\begingroup$ That answer is correct, and my answer is also technically correct, but I didn't realize that the value of $k$ that solves $c^k + (1-c)^k = 1$ is just $k=1$. So the answer is in fact $\Theta(n)$. $\endgroup$ – Misha Lavrov Mar 24 '17 at 19:04
  • $\begingroup$ I see, your answer helped me anyway to see how to prove it so thank you :) $\endgroup$ – Evyatar Mar 24 '17 at 20:46

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.