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)