$$ T(n) = T(n-a) + T(a) + cn $$
Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$
And I don't understand why. Maybe I didn't understand the withdrawal formula as needed.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Your recurrence expands into a recurrence tree in the following way. Each node has a label. If the label $n$ is $a$ or smaller, then the node is a leaf. Otherwise, the node has two children, one labeled $n-a$, the other one labeled $a$.
Suppose that you create this tree starting with a root labeled $n$. The root has two children: one is labeled $n-a$, and the other one, labeled $a$, is a leaf. The node labeled $n-a$ has two children, one labeled $n-2a$, and the other one is a leaf. And so on.
It takes roughly $n/a$ steps until this process terminates (since we start with $n$, have to get to $a$ or less, and drop by $a$ each time). Therefore the height of the tree is roughly $n/a$.