Can someone explain the recurrence relations for quad and binary partitions for searching in a sorted table?

Question

If you have a square region that holds various numbers, what is the result of each recurrence relation?:

T(n) = 3T(n/2) + c and T(n) = 2T(n/2) + cn

I know the first is supposed to result in a quad partition and the second a binary partition, but I can't intuitively wrap my head around why this is the case. Why are we making 3 recursive calls in the first case and 2 in the second? Why does the +c or +cn effect what we're doing with the problem?

Answer 1

I think this is what you are looking for

http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html

if your question is just about the recursion explanation, I recommend reading up on solving recurrences using recursion tree and the master method

http://courses.csail.mit.edu/6.006/spring11/rec/rec08.pdf

This explains the second recurrence and the method. Basically you will have a recursion tree with height (lgn) and the cost at each level equalling n.

In the first one the recursion tree will have run time of the order of number of nodes in the tree. The height will still be lgn but the cost at each level 3^h * c. Summation over this will give you the complexity