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. 

Unwinding

I'm really sorry for inactive blog for about one month. So there are a lot of things to talk about. Hence, I will split this week blog to three blogs to cover up my pass weeks.

First, I want to talk about my experience in proving limit from a recursion function. The number of recursion function can be called  is in between its best case scenario to worst case scenario. Hence, in order to proof  the limit, first we need to find closed form of recursion function. Then we need to find the best case and worst case scenario for that closed form.

From my experience, getting closed form is the hardest thing to do in proving the limit of recursion function. Even though prof, taught us to do unwinding steps before getting to closed form but it is quite hard to see the pattern from unwinding. In order to recognize the pattern I need to do quite a lot of revision of my previous calculus subject. Even if I do recognize the pattern there is another problem, finding the closed form. Sometime, the pattern is obvious and we can straight away get the closed form, but sometime the pattern is obvious but not the closed form. For example Fibonacci sequence because the pattern might be to see, but getting closed form is not easy.

So in the next blog I will talk about getting limit of the closed form. However, once you found closed form the next problem is just a cake walk :D