+2 votes

Solve the recurrence relation: T(n) = 3 T(n/2) + n1.5 log n

in Divide & Conquer by AlgoMeister (1.6k points)

4 Answers

0 votes
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 )
by AlgoMeister (584 points)
edited by
0 votes
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)
by AlgoMeister (876 points)
0 votes

a = 3, b = 2, f(n) = n1.5 log n

Using Master's Theorem,

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

n1.58 > n1.5 log n [ To check we can take any value for n, say n = 2 and verify. ]

Therefore, T(n) = O(n1.58)

by AlgoStar (404 points)
0 votes
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)
by (132 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...