Understanding recursion tree for withdrawal formula

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

• What would the withdrawl/withdrawal formula be? If you don't tell us, we cannot possibly know what you mean by it. Try to put yourself in our shoes. – Yuval Filmus May 6 '20 at 7:12

1 Answer

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