Analysis of the algorithms

68 views
T(n) = 3T( n/3 ) + n/2

The answer to the above question says that case 2 of masters theorem is applied here. How is it so?

T(n) = aT(n/b) +cnk

here,  T(n) = 3T( n/3 ) + n/2

k=1 ; c =1/2 ;  a=3 ; b=3

a = bk

3  = 31

Complexity = nklogn

= O(nlogn)

1 vote

Case 2: f(n) = nclogkn   c=  $\log_b a$

c=1

$\log_b a$ =1

Related questions

1
201 views
I want to learn to find time complexity of the recurrence relation of an algorithm. Please suggest some good links or any gatetoverflow imp questions links to look as examples . Thanks