Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#1 2013-01-09 22:09:06

azair
Novice

Offline

Help!!! Master Theorem?

Hello everyone wave, 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???dizzy]

{I'm assuming this tutorial's topic as : MASTER THEOREM FOR DUMMIES. big_smile}
Thanking you in advance...

#2 2013-01-10 01:56:38

anonimnystefy
Real Member

Offline

Re: Help!!! Master Theorem?

What do you mean by log^p?


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

#3 2013-01-10 19:33:40

bob bundy
Moderator

Offline

Re: Help!!! Master Theorem?

I think it is



What I don't follow is the theta function notation.  Do you recognise that?

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

#4 2013-01-10 23:40:01

anonimnystefy
Real Member

Offline

Re: Help!!! Master Theorem?

I do. It means that the function T(n) grows the same way as the function isnide the theta...

I think somethong is wrong either with tthe logarithms or with the conditions for p in the second case (a=b^k)...

Last edited by anonimnystefy (2013-01-10 23:43:12)


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Board footer

Powered by FluxBB