Solve the following recurrence relation using master method.

Question

Suresh Chand · Accepted Answer

a) T(n) = 7 T(n) + n2 Solution: Here we have a = 7, b = 2 and f(n) = n2 Now, nlogba = nlog27 = n(log 7 / log 2) = n2.8 Also, f(n) = n2 Since f(n) ≤ nlogba-c where choose ε = 0.1 Thus it satisfies the first case of Master's method. Thus it's complexity, T(n) = Θ( nlogba ) = Θ( nlog27 ) = Θ(22.8) Thus, T(n) = Θ(n2)   b) T(n) = 4 T(n/4) + kn Solution: Here, we have a = 4, b = 4 and f(n) = kn Now, nlogba = nlog44 = n(log 4 / log 4) = n1 Also, f(n) = kn1 Since f(n) = nlogba Thus it satisfies the third case of Master's method. Thus it's complexity, T(n) = Θ( f(n) log n) = Θ (kn log n) Thus T(n) = Θ (n log n)

Solve the following recurrence relation using the master method.

T(n) = 7 T(n) + n²

T(n) = 4 T(n/4) + kn

Leave your Answer:

Hits Counter

Question

Solve the following recurrence relation using the master method. T(n) = 7 T(n) + n2 T(n) = 4 T(n/4) + kn

Leave your Answer:

Solve the following recurrence relation using the master method.

T(n) = 7 T(n) + n²

T(n) = 4 T(n/4) + kn