I blog on blogger now

Yeah, if you want to see what I write nowadays find it over at my blog. I find it easy to write the posts in Stackedit and then push to blogger easily. I prefer Stackedit due to it being great for writing in Latex.

 

Advertisements

Master Theorem

Master theorem, sounds swell doesn’t it.  Let me tell you what this theorem means,

There are a class of algorithms known as divide and conquer (D&C)  which works by dividing a problem into sub-problems of smaller size after which we conquer each sub-problem recursively and combine these solutions.

We use Master theorem to find the running time of D&C algorithms, whose recurrence relation is of the form,

Here, since an algorithm’s performance time may vary with different inputs of the same size, one commonly uses the worst-case time complexity of an algorithm, which is denoted as T(n).

In this case,  the recurrence relation is just an equation which tells us that the worst-case time complexity of a D&C algorithm when faced with a problem of size n  will be the sum of

f(n) – which represents the cost of recombining the solutions to the a sub-problems at that level. This will change depending on the algorithm used.

and

a \times T( \dfrac{n}{b} )  – which represents the recursive cost due to each of the sub-problems of  \dfrac{n}{b}   size.

When I say recursive cost I mean that this same situation repeats itself, see in the image below (borrowed from CLRS ). The equation given above in its current form applies to the entire tree, but if we were to consider any of the sub-problems as a problem by itself, we could just as easily rewrite the recurrence relationship changing the size involved.

Keep an eye on this image, It will serve as a important tool to visualize the process.

fig104_01_0

I will now be delving into deriving the theorem, for that we need to be clear on what type of problems we will be analyzing,

what happens is that we take a problem of some input size n, 

divide that problem into sub-problems each of size  \dfrac{n}{b} , 

then take each of the a sub-problems and further divide each of them into sub-sub-problems, so now we have a total of a^2  sub-sub-problems, each of size   \dfrac{n}{b^2}  .

From the image we can see how this will play out, just consider n_1  as  \dfrac{n}{b}  ,   and  n_2  as  \dfrac{n}{b^2}   and so on …

Here we can think of  as a measure of spread of the algorithm, the number of recursive branches that spawn at any level i is proportional to   a^i   which is the number of sub-problems at the level i.

Now consider b, this is a measure of decrease in the problem size, at any level i the problem size will be  \dfrac{n}{b^i}  . 

Just to be clear  i is  an index I am using to the various levels of the tree.

This begs the question, what are the values that i will take, it should be obvious that i = 0 is the initial state when the problem starts with size of   \dfrac{n}{b^0} which  is just n, and at this “0” level we have  a^0  i.e.  1 problem, this progresses as i increases.

As with all recursive strategies we need a base case, the upper limit of i is the level at which leaf nodes of the tree structure you see in the figure appear.  So to obtain them we will be breaking the problem into smaller sub-problems over and over again by a factor of b until they are of Unit size.

Thus each of such problems ( the leaf nodes ) can be solved in O(1) time as shown in the image. But there will be   a^j   number of such problems, where j is the final level of the structure.

What’s the value of j ?  well we know the size  of the problems at level  is   \dfrac{n}{b^j}  which is supposed to be equal to 1.  So,

  n = b^j

Applying log on both sides,

log (n) = j \times log (b)

Bringing  j to a side, we get

j = \dfrac{log(n)}{log(b)}\log_b n .

So we have got the value to which will increase to, now unless n is an exact power of b, j will not be an integer causing the following calculation to become more complicated.

Thus, assuming n is an exact power of b, ( the other complete proof is available in CLRS,  its pretty similar except we need to introduce floor and ceiling functions. )

Lets now consider the “cost” attributed to the entire algorithm, It can be thought of as being the sum of the cost due to the internal nodes and the leaf nodes.

The cost due to all the internal nodes is the sum of the cost at each level, at any level i  the cost will be

( number of nodes at the level i )  \times  ( cost due to each node )    which  is

Cost at a level i =  a^i\times f(\dfrac{n}{b^i})

Here the cost due to each node will be a function of the size of that problem, as this is the cost of combining the solutions of the sub-problem.

Total cost due to internal nodes : –

= \sum\limits_{i=0}^{j-1} a^i\times f(\dfrac{n}{b^i})  =  \sum\limits_{i=0}^{\log_b n-1} a^i\times f(\dfrac{n}{b^i})

Thus as we can see we have considered i = 0  till j – 1,  at i = j  we have the last level consisting of   a^{\log_b n}  leaf nodes.

Yeah so we have    n^{\log_b a}    number of leaf nodes,

wait what?! how? lets try applying this law;    ea459fa36dbf8509f6b46143ddf40251

K = a^{\log_b n} = a^{\dfrac{\log n}{\log b}}

 

Now applying  log  n  both sides,

\log K = \log a \times \dfrac{\log n}{\log b} = \log_b a \times \log n = \log n^{\log_b a}

 

Thus,  taking Antilog,

K = n^{\log_b a}

 

Thus Total cost due to all leaf nodes : –

=   ( number of leaf nodes ) \times ( cost due to each node )

Assuming we solve the problems of unit size in constant time we get

O(n^{\log_b a} )

 

Now that we have the cost in terms of any general algorithm, In terms of the recursion tree, lets analyse the three cases which depend on how the total cost is distributed.

When faced with a D&C algorithm,

consider the recurrence relation to be

Untitled

 

which we are required to analyse we need to plug it into one of these 3 cases, here the f(n)  of the recurrence relation will tell us under which of the three cases that particular algorithm falls under.

(1) The Total cost is dominated by the costs in the leaves nodes

68a9844f1042ce64f7e49bef593a7657  where  3912a9146c4c49c32c2c0e6d59369fe5

(2) The total cost is evenly distributed among the levels of the tree

74b0272730287ce50d438c4c3f0013cb  where  6b61c387c2164cd31329d0cc6704ec00

(3) The total cost is  dominated by the cost of the root nodes

18ed92e71d10ddc3a9a8d1ff6d0ad0f3  where  0d543ce7b07ed3bf3f030a56a8d840dd

It should be clear why the functions have to as specified above, at the balancing point the cost due to leaf node and internal nodes are equal we get case two, but if f(n) is such that either of them is larger we get a separate case.

We have different symbols to show f(n) in each of the 3 cases, this is due to the time complexity .

 

Untitled

So in short, when faced with a recurrence relation of a D&C algorithm we can easily find its running time in  Θ-notation.

Any suggestion towards improvement is welcome.

My Anime Reviews

 
  • One Piece
  • This was the anime which could be said to have started my addiction! I enjoyed this anime so much that I started downloading it! Its mainly a fun anime with a very thrilling storyline, with plenty of comic scenes and epic battles between people with really crazy powers.But to me its strongest point is the amount of suspense, because of its fast paced storyline you will want to see the next episode.Believe me unlike naruto the story never lags, and oda always manages to both surprise and amuse us.

    but you may feel the initial episodes kinda, hmm… slow? anyway.. push through! and you will be rewarded!

    A battle to remember!
    A battle to remember!
     
  • Death Note
  • This is the anime which is the one I would recommend to anyone who is yet to start watching anime as it is a prime example that lets you see the potential of anime as an art, a method of storytelling. This anime’s main attraction is also its gripping story, with no loopholes.We have a protagonist who is too clever for his own good! we see the levels to which a cat and mouse game can reach.

     

    The whole cast :p
    The whole cast :p

     

  • Naruto
  • This was one the first anime I had watched, I had really liked it then and got the time to finish it only after I got into a college, This anime is one of the most popular shonen anime of all time, it features a very intricate storyline with a lot of twists and exciting fights, there is a very solid structure in which various powers are held by the characters and most characters are relatable in terms of motive. They explore concepts like friendship, loss of loved ones, being isolated from society, revenge etc in a not so obvious way. The anime has a fatal flaw of trying to fatten the storyline with “fillers” ie episodes not relevant to the main storyline, some of these can be said to serve the purpose of fleshing out the characters. Most of these episodes were in my (and a lot of others opinion) a total drag. Still as of the last episode I watched (371 – shippuden) The wait was really worth it, things are heating up! On the whole naruto was actually totally Awesome!!

     

    The first arc
    The first arc

     

  • Code Geass
  • This anime is as I have seen the only anime that comes close to , nah totally beats death note in its particular genre of ultra intelligent protagonists who use complicated strategies, it beats death note (in my opinion) only because of its Kick-ass ending. (Yes its Awesome!) So code geass there is both R1 and R2 (2 seasons), it also (like most anime’s which makes you think) has a clean set of rules under which the particular “power” can be used, this ensures that we can get absorbed into the storyline as we can follow all the decisions the protagonist makes as he has to play by the rules. Here themain topic being explored would have to be how all humans are different and if the strongest will survive rule is “right” as are societies ment to help the weak? they ask you to think about the various facets of involving Social Darwinism.

    A gem of an anime!
    A gem of an anime!

     

  • Full Metal Alchemist
  • Well this is among all the top anime lists across the internet, and rightly so! This series is (as far as I know & and have seen heard ) the ONLY anime that you should watch in english Dub,
    Most english dubs are lame, they fail to convey the emotions of the characters properly, ok even I used to watch anime with english audio! hell i didn’t understand japanese one bit, but then as naruto (shippuden – second season) did not have english dub after a number of episodes I had to watch it in english subtitles. And even though initially I was uncomfortable i have to say it is way way better! See you also get to learn a new language. Naruto itself has run for 220 episodes and Naruto shippuden is at 371, One Piece is at 653! 😀 (all of 25 mins each). this is just 2 series! the more you watch soon you will be able to understand japanese and maybe even speak rudimentary japanese.
    Ok anyway these guys did a superb job of english dubbing this series,The series is based on Alchemy, as you hear in the opening song,
    “Human kind can not gain anything without first giving something in return. To obtain something of equal value must be lost. That is Alchemy’s first law of equivalent exchange. In those days we really believed that to be the world’s one and only truth, But the world isn’t perfect, and the law is incomplete. Equivalent Exchange does not encompass everything that goes on here, but I still chose to believe in its principle: that all things do come at a price, that there’s an end and a way, that the pain we work through did have a reward, and that anyone who’s determined and perseveres will get something of value in return, even if it’s not what they’re expecting. I don’t think of Equivalent Exchange as a law of the world any more. I think of it as a promise between my brother and me, a promise that someday we’ll see each other again. “
    -Alphonse Eric
    It also has my favorite theme song! I totally fell in love with it.

    The awesome powers, and he's too cool too!!
    The awesome powers, and he’s too cool too!!

    This is basically a copy from My site.

    Hello Universe!

    well, I have long wanted to write a blog..

    I think a lot and had started inking  typing my thoughts onto my google keep.

    I never really got around to setting up the blog, well now I have I hope to be able to put up my ideas

    thoughts, views etc onto the internet, hopefully immortalize it… :p