Question

What is the solution of the recursive equation T (n)= 3T n +n2? 4 a) O(nlog n) b) O(12 193) 0.793 c) O(17") d) O(n log n)

Answer 1

Answer:

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence

T(n)=3T(n4)+n⋅log(n)

by applying the Master Theorem.

I am very confused by how it is done. So, a=3,b=4,f(n)=n⋅log(n)

First step is to compare nlogba=nlog43=O(n0.793) with f(n).

I have no clue on how they compared this. The book explains:

f(n)=Ω(nlog43+ϵ), where ϵ≈0.2, case 3 applies if we can show that the regularity condition holds for f(n).

Followed by:

For sufficiently large n, we have that: af(nb)=3(n4)log(n5)≤(34)nlogn=cf(n) for c=34.Where did 3(n4) come from?

share improve this question follow

asked

Sep 11 '12 at 3:32

newprint

441●11 gold badge●55 silver badges●1010 bronze badges edited

Sep 28 '13 at 12:36

Gilles 'SO- stop being evil'

39.2k●77 gold badges●103103 silver badges●167167 bronze badges

1 Answer

order by

Up vote

11

Down vote

Accepted

If our recurrence takes the form T(n)=aT(n/b)+f(n), then to use the "third case" of the Master method we must have the following hold:

f(n)=Ω(nlogba+ϵ) for some ϵ>0 and if af(n/b)≤cf(n) for some constant c<1 and all sufficiently large n, then T(n)=Θ(f(n))

Our recurrence is defined as

T(n)=3T(n/4)+nlogn.

By definition we have, a=3,b=4,f(n)=nlogn.

We now need to show that f(n) is polynomially larger than nlogba. That is the "f(n)=Ω(nlogba+ϵ)" part from above. Defining ϵ≈0.2 achieves this. The reason being that log43≈0.793 and f(n)=Ω(n0.793+ϵ).

We are left to show that f(n) satisfies the regularity condition. That is the "af(n/b)≤cf(n) for some constant c<1 and all sufficiently large n" part.

We simply plug in our values of a,b to get:

af(n/b)=3(n/4)log(n/4).

All we did was take the "n" in f(n) and plug in "n/4".

To make this easier to see, let k=n/4 and observe that af(k)=aklogk. Swapping k with n/4 we have

3(n/4)log(n/4)≤(3/4)nlogn=cf(n)

where c=3/4.

This finishes our necessary requirements and we have that T(n)=Θ(nlogn).

Explanation:

plz follow me