How to determine the height of a recursion tree from a recurrence relation?

Answer 1

The height of the recursion tree depends on the recursive algorithm in question. Not all divide and conquer algorithms have uniformed height trees, just as not all tree structures have uniform heights. If you cannot determine the maximum possible height of the algorithm, or if you need to calculate the actual height of the tree at run time, you can use a variable global to the recursive function, increment it upon the entry to the function, and decrement it upon the function exit. This variable will indicate the current level of the recursive procedure. If necessary, you can maintain the maximum value of this variable in a second variable.

Answer 2

Firstly, if this is a homework question, please mark it as such. The images you link to imply that you're in CS 455, with Professor Wisman. :)

The main hint I'll give is this: The height of the tree is obviously determined by when you get to the "leaves". The leaves of a tree modelling the recurrence relation of a function are the base case. Thus, I would look towards seeing how "quickly" N can shrink to the base case.

Answer 3

If recurrence is in the form of T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

For example, 2T(n/2) + n recurrence would have tree of depth lg(n) (log base 2 of n).