I need to Find the solution of the recurrence for n, a power of two if T(n)=3T(n/2)+n
for n>1 and T(n)=1 otherwise.
using substitution of n=2^m,S(m)=T(2^(m-1))
I can get down to:
S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+⋯+3^(m-1) 2^1+3^m
But I have no idea how to simply that.
These types of recurrences are most easily solved by Master Theorem for analysis of algorithms which is explained as follows:
Let a be an integer greater than or equal to 1, b be a real number greater than 1, and c be a positive real number. Given a recurrence of the form -
T (n) = a * T(n/b) + nc where n > 1, then for n a power of b, if
English translation of your recurrence
The most critical thing to understand in Master Theorem is the constants a, b, and c mentioned in the recurrence. Let's take your own recurrence - T(n) = 3T(n/2) + n - for example.
This recurrence is actually saying that the algorithm represented by it is such that,
(Time to solve a problem of size n) = (Time taken to solve 3 problems of size n/2) + n
The n at the end is the cost of merging the results of those 3 n/2 sized problems.
Now, intuitively you can understand that:
From the above three intuitive understanding, only the three cases of Master Theorem arise.
In your example, a = 3, b = 2 and c = 1. So it falls in case-3 as Logba = Log23 which is greater than 1 (the value of c).
The complexity therefore is straightforward - Θ(nlogba) = Θ(nlog23).