Master Method

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.
Anyways, Let's get started.

MASTER METHOD (MASTER THEOREM)

 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:

• The Problem should be a divide and conquer problem.
• Since it is a divide and conquer problem, It must be expressed as a recurrence.

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:

• Dividing the problems into numerous sub problems (which are like the version of big problem but smaller in size).
• Conquer the sub problems (solve the sub problems).
• Solve the bigger problem by combining the solution of the smaller sub problems.

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.
So, a general recurrence relation (for which I'll describe my version of Master Method) is:
T(n) = a * T(n / b) + O(n^d)
Here, O(x) stands for BIG OH of x!
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".
now for this to be a valid recurrence, we should have a >= 1, b >1 and d can be any integer >= 0
Now three cases arise, based on the comparison of " a" and "b^d"

• If a = b^d then, the complexity is O(n^d log(n) )
• If a < b^d then, the complexity is O(n^d)
• If a > b^d then, the complexity is O(n^(log(a) to base b))   

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.
Till then sayonara!

Hello World!

"HELLO WORLD\n"

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.