Divide and Conquer!

   As I promised in last blog, in this blog I will talk about the limit of number of time the recursion function is called.

   There is two way of getting the limit of recursion function. In first way, I must get a closed form of  the recursive function, then from that I can deduce the either worst case scenario or best case scenario. Then I will use the first case scenario I've proved to prove the other case scenario.  This is fairly simple and intuitive.

   However, I can't get closed form all the time, and even if there is closed form, there is another way of proving the limit without getting closed form. In that case, Master Theorem will be very useful. The Master Theorem is very useful when I'm doing divide and conquer. "Divide" involves breaking the array or list in a particular manner. While in conquer part, I've to worry about additional steps that involved with combining all the "divided".

Master Theorem looks like :

               Assume T(n)        = k                                                      if  n<B

                                             = a₁T(n/b_k) + a₂T(n/b_k) + f(n)          if  n>B

               T(n)        = θ(n^d)                 if a < b^d

                              = θ(n^d log n )      if a = b^d

                              = θ(n^log­_b^a)           if a > b^d

               Hence, a = a₁ + a₂

                              b = b_k

                              d = power of limit of f(n)

   For more information about Master Theorem http://en.wikipedia.org/wiki/Master_theorem. The link helped me to understand better about Master Theorem.