Answer to Question #224901 in Discrete Mathematics for Piu

Question

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

Answer 1

a) cost level 1 = c(n/4)² + c(n/4)² +c(n/4)² = (3/16) cn²

cost level 2 = c(n/16)² *9 = (9/16²)cn²

n/4^x =1

Xlog4 =logn

Last level

nlog₄3*T(1)=θ(n^log₄³)

= cn²(1+(3/16) +(3/16)² + -----+θ(n^log₄3)

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

Solving it

16/13cn²(1-(3/16) ^log₄n+θ(n^log₄3)

=O(n²)

b) From the master theorem

T(n)=aT(n/b) + n^c 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

log_ba =log_3/21 =0=c

T(n) ϵ θ(logn)

Using k=0

n⁰ =log n⁰ =1

1ϵ θ(n⁰log⁰n)