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

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 6 at 7:12

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.