Question

Solve the recurrence relation: T(n) = 3 T(n/2) + n^1.5 log n

Answer 1

a=3; b= 2;
log_b(a)= log_2(3)= 1.5849
n^1.58 > n ^1.5
Therefore,
T(n) = theta (n^1.58 )

Answer 2

Using masters theorem we get answer as theta(n^1.58) .

As a = 3 , b =2  => log_b(a)= log_3(2)= 1.58

but f(n) = n^1.5 logn

clearly 1.58 > 1.5

so answer is  theta(n^1.58)

Answer 3

a = 3, b = 2, f(n) = n^1.5 log n

Using Master's Theorem,

log_b(a)= log_2(3)= 1.58.

n^1.58 > n^1.5 log n [ To check we can take any value for n, say n = 2 and verify. ]

Therefore, T(n) = O(n^1.58)

Answer 4

Given, T(n) = 3T(n/2) + n^1.5 log n

Using Master's theorem,

a=3, b=2, f(n) = n^1.5 log^1 n , here k=1.5, p=1

Calculating log a base b = log 3 base 2 = 1.58, k=1.5

Clearly log a base b > k (case 1)

T(n)  = theta(n^log a base b)

T(n) = theta(n^1.58)