finding asymptotic complexity of T(n)=T(cn)+T((1-c)n)+1 0The 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?
 A: 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^*$. 
