Solving Recurrences

(obtaining upper bounds)

Merge Sort:

T (n) = Q (1 )  for n = 1 (this is the boundary condition)

         = T (  é n/2 ù ) + T ( ë n/2 û ) + Q (n )

Since T (n) is Q (1 ) for all sufficiently small n, we often ignore boundary conditions.

Next we look at some methods.