tag:blogger.com,1999:blog-60160904220952814122017-07-29T19:37:57.915+05:30Piyush MishraThis is my personal blog.Piyush Mishranoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6016090422095281412.post-18356758244842833992014-11-04T22:26:00.001+05:302014-11-04T22:37:46.286+05:30Master Method<div dir="ltr" style="text-align: left;" trbidi="on">In this post, I would like to share my knowledge of the Master Method also called as the Master Theorem. By no means I am a pure computer scientist so do not expect me to be cent percent correct and thorough.<br />Anyways, Let's get started.<br /><blockquote class="tr_bq"><b>MASTER METHOD (MASTER THEOREM)</b></blockquote> First a bit about it. Master Method is a method (surprise!huh!) which can be used to get an upper bound on the time complexity of a problem. There are a few constraints though:<br /><br /><ul style="text-align: left;"><li>The Problem should be a divide and conquer problem.</li><li>Since it is a divide and conquer problem, It must be expressed as a recurrence.</li></ul>Now, some of you might wonder, what is a divide and conquer thing and WTH is recurrence. Well calm down disturbed souls. A divide and conquer problem is basically a problem which can be solved by:<br /><br /><ul style="text-align: left;"><li>Dividing the problems into numerous sub problems (which are like the version of big problem but smaller in size).</li><li>Conquer the sub problems (solve the sub problems).</li><li>Solve the bigger problem by combining the solution of the smaller sub problems.</li></ul>I will delve into the details of Divide and Conquer and recurrence in a separate post, but for now I'll assume that you have a given recurrence relation and you want to know the time complexity of it, without paining your mind.<br />So, a general recurrence relation (for which I'll describe my version of Master Method) is:<br />T(n) = a * T(n / b) + O(n^d)<br />Here, O(x) stands for BIG OH of x!<br />and "a" is the number of sub problems, "b" is the extent to which the bigger problem is divided into sub problems and "d" is the exponent of "n".<br />now for this to be a valid recurrence, we should have a >= 1, b >1 and d can be any integer >= 0<br />Now three cases arise, based on the comparison of " a" and "b^d"<br /><br /><ul style="text-align: left;"><li>If a = b^d then, the complexity is O(n^d log(n) )</li><li>If a < b^d then, the complexity is O(n^d)</li><li>If a > b^d then, the complexity is O(n^(log(a) to base b)) </li></ul>Well, I am sorry for the bad formatting and how badly I have written all those math equations. I promise you (yep, I am not into politics) I will come back and edit and format this post better and might power it with some TEX power.<br />Till then <b><a href="http://en.wiktionary.org/wiki/sayonara">sayonara</a>!</b></div>Piyush Mishrahttps://plus.google.com/101945922723335148144noreply@blogger.com0tag:blogger.com,1999:blog-6016090422095281412.post-26301075377244471342014-10-13T01:51:00.001+05:302014-10-13T01:51:12.781+05:30Hello World!<div dir="ltr" style="text-align: left;" trbidi="on"><span style="font-size: large;">"HELLO WORLD\n"</span><br /><span style="font-size: large;"><br /></span>Alas! it happened. Finally I am writing a blog. After years of procrastination today I gathered all my willpower to finally achieve the unbelievable. Its just the start. I plan to write my day to day happenings, experiences and things I am passionate about on not so daily basis. </div>Piyush Mishrahttps://plus.google.com/101945922723335148144noreply@blogger.com1