How to Solve: T(n) = 2 T(n/4) + T(n/4) + T(n/4) + 311 via The Master Theorem?

Question

I really couldn't solve this because it was kinda tricky to me (as a new one to Master theorem).Any help would be greatly appreciated!

Answer 1

I've never heard of the master theorem before. But I read this when I googled it:

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

where, T(n) has the following asymptotic bounds:

1. If f(n) = O(n^(log_b a-ϵ)), then T(n) = Θ(nlog_b a).

Here, a=4; b=4; So log_b(a)=1.

Here, f is O(1), so epsilon=3 for log_b(1)=0 and n^0=1.

So it looks like T(n) is O(n).