Mixed Recurrence How to solve the following mixed recurrence relations:
$$T(n)= \max_{0<k<n} \left\{ \min \left\{ k, a T\left(\frac{n-k}{b}\right)\right\} \right\}$$
Here $a,b \ge 1$ are constants.
I could solve some special cases such as when $a=b=2$ then by guessing method, $T(n) = \Theta (\dfrac n {\lg n})$. However, I could not generalize for all values of $a,b$.
 A: Since you did not define starting values of $T$ and didn’t care about divisibility $n-k$ by $b$, I think a solution by asymptotical handwaving is OK for your needs. Assume that $T$ increases. If $a=1$ then the right hand side of the equality for $T(n)$ is less than $T(n)$, so from now we shall assume that $a>1$. Since when $k$ increases $ aT\left(\frac{n-k}{b}\right)$ decreases, we have $T(n)=k=aT\left(\frac{n-k}{b}\right)$ for some $k\in (0,n)$. Let’s look for a solution of this equality with a simple form. The following cases are possible.
$a>b$. Assume that $T(n)\simeq cn$ for some constant $c<1$. Then $$k\simeq cn \simeq ac\frac{n-cn}{b},$$  so we can put $c=1-b/a$. 
$a=b$. Assume that $T(n)\simeq \frac{n}{\ln n}$. Then $$k\simeq \frac{n}{\ln n}\simeq a\frac{\frac{n-\frac{n}{\ln n}}{b}}{\ln \left(n-\frac n{\ln n}\right)}\simeq \frac{n}{\ln n}.$$
$a<b$. Assume that $T(n)\simeq n^c$ for some constant $c<1$. 
Then $$k\simeq n^c \simeq a\left(\frac{n-n^c}{b}\right)^c\simeq a \left(\frac{n}{b}\right)^c,$$ so we can put $c=\log_b a$. 
