Can T(n) = 3T(n/2) + c T(1)=0, solved using master theorem? If yes, I am struggling on understand master theorem now, could someone tell me which case it falls to and why.
There are different possible approaches for the master theorem. I like the one proposed by Cormen et al. in their book Introduction to Algorithms.
Now we need to compare f(n) with n^(logb(a)) .
Note that the three cases do not cover all the possibilities for f(n). There is a gap between cases 1 and 2 when f(n) is smaller than n^(logb(a)) but not polynomially smaller. Similarly, there is a gap between cases 2 and 3 when f(n) is larger than n^(logb(a)) but not polynomially larger. If the function f(n) falls into one of these gaps, or if the regularity condition in case 3 fails to hold, you cannot use the master method to solve the recurrence.
Now to solve the recurrence in question...
a=3, b=2, f(n) = c = n^0
so we have n^(log2(3)) ≈ n^(1.58) which is polynomially larger than n^0, falling under the 1st case. Then the time complexity is T(n) = Θ(n^(logb(a))) --> T(n) = Θ(n^1.58)