retagged by
1,278 views
0 votes
0 votes
$T(n) = 3 T (\frac{n}{4}) + n$
retagged by

1 Answer

0 votes
0 votes

Master’s Theorem .

Let a and b be positive constants and let T(n) = aT(n/b) + cn^k for n > b then

• if a > b^k then T(n) is Θ(n^ logb a )

• if a < b^k then T(n) is Θ(n^ k )

• if a = b^k then T(n) is Θ((n^ k )(log n))

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

a=3 b=4 k=1

3<4^1 so case 2:

 T(n)=Θ(n)

Related questions

2 votes
2 votes
2 answers
1
2 votes
2 votes
1 answer
4