Hello everyone
, I am learning an Algorithm analysis on my own and today I came across 'Master Theorem for Divide and Conquer'. Since I'm quite not good at Mathematics, this topic is giving me a full headache.(ahem ahem, no offense please!!! ;-)).
Alright, The definition is given as follows :
"If the recurrence is of the form T(n)=aT(n/b)+Θ(n^k log^p n),where a>=1, b>1, k>=0 and p is a real number, then:
1.) If a>b^k, then T(n)=Θ(n^log^a↓b) [Note : lets assume ↓ as base.]
2.) If a=b^k :
a.) If p>-1, then T(n)=Θ(n^log^a↓b * log^p+1 n)
b.) If p=-1, then T(n)=Θ(n^log^a↓b * loglog n)
c.) If p<-1, then T(n)=Θ(n^log^a↓b).
3.) If a<b^k :
a.) If p>=0, then T(n)=Θ(n^k log^p n)
b.) If p<0, then T(n)=O(n^k).
"
Well can anyone help me explain what these means in simple terms with an example if possible.
For example : Problem--> T(n)=2T(n/2)+nlogn. [The Answer is Θ(nlog logn) :? How???
]
{I'm assuming this tutorial's topic as : MASTER THEOREM FOR DUMMIES.
}
Thanking you in advance...