Solution to Solve the recurrence by master's method. a) T(n) = 3T[n/4)+ cn^2 b) T(n)=T[2n/3)+1 - Sikademy
Author Image

Archangel Macsika

Solve the recurrence by master's method. a) T(n) = 3T[n/4)+ cn^2 b) T(n)=T[2n/3)+1

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

a) cost level 1 = c(n/4)2 + c(n/4)2 +c(n/4)2 = (3/16) cn2

cost level 2 = c(n/16)2 *9 = (9/162)cn2

n/4x =1

Xlog4 =logn

Last level

nlog43*T(1)=θ(nlog43)

= cn2(1+(3/16) +(3/16)2 + -----+θ(nlog43)

(1+(3/16)+ (3/16)+---) forms an infinite geometric progression

Solving it

16/13cn2(1-(3/16) log4n+θ(nlog43)

=O(n2)

b) From the master theorem

T(n)=aT(n/b) + nc where a is the coefficient of T from the equation b is the number dividing n and c is the number raised to n at the end term from the equation a=1 b=3/2 and c=0

logba =log3/21 =0=c

T(n) ϵ θ(logn)


Using k=0


n0 =log n0 =1


1ϵ θ(n0log0n)


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-2719-qpid-1189