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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**azair****Member**- Registered: 2013-01-08
- Posts: 3

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...

☁ ♪ ☁☁♪♫☁

♫☁☁♪ ☁

❄ Music in the Sky ❅

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,657

What do you mean by log^p?

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

**bob bundy****Moderator**- Registered: 2010-06-20
- Posts: 6,528

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

Offline

**anonimnystefy****Real Member**- From: The Foundation
- Registered: 2011-05-23
- Posts: 15,657

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 00:43:12)*

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Offline

Pages: **1**