The Gateway to Computer Science Excellence
0 votes
46 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?
in Algorithms by Junior (567 points) | 46 views

2 Answers

+3 votes

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)

by Active (2.3k points)
+1 vote

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

c=1

 $\log_b a$ =1

by Active (3.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,293 answers
198,233 comments
104,916 users