Question

Write down the Recurrence Relation for binary search tree; solve it using the iterative method and give an answer at the end in asymptotic form.
Note: need to show all possible steps.

Answer 1

A recurence refers to the recursive definition of function. Similar to the recursive structures, a reference has more than one recursive case or base case.

Each of the case has an equation which consists of some function value f(n). the base cases however has usually finite explicit values.

Each of the recursive cases can therefore relate to the function value f(n).