# finding asymptotic complexity of T(n)=T(cn)+T((1-c)n)+1 0<c<1

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

• Thank you so much for your time Misha! – Evyatar Mar 24 '17 at 17:15
• 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 – Evyatar Mar 24 '17 at 17:22
• Wait, I'm really stupid. – Misha Lavrov Mar 24 '17 at 19:03
• 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)$. – Misha Lavrov Mar 24 '17 at 19:04
• I see, your answer helped me anyway to see how to prove it so thank you :) – Evyatar Mar 24 '17 at 20:46