Solving a recurrence: T(n)=3T(n/2)+n

Question

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.

Solution 1

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) + n^c where n > 1, then for n a power of b, if

1. Log_ba < c, T (n) = Θ(n^c);
2. Log_ba = c, T (n) = Θ(n^c * Log n);
3. Log_ba > c, T (n) = Θ(n^log_ba).

---

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:

• if the cost of "solving 3 problems of size n/2" has more weight than "n" then the first item will determine the overall complexity;
• if the cost "n" has more weight than "solving 3 problems of size n/2" then the second item will determine the overall complexity; and,
• if both parts are of same weight then solving the sub-problems and merging their results will have an overall compounded weight.

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 Log_ba = Log₂3 which is greater than 1 (the value of c).

The complexity therefore is straightforward - Θ(n^log_ba) = Θ(n^log₂3).

Solution 2

You can solve this using Masters theorem, but also by opening the recursion tree in the following way:

• At the root of the recursion tree, you will have a work of n.
• In the second stage, the tree splits into three parts, and in each part, the work will be n / 2.
• Keep going until you reach the leaves. The entire work leaf will be: O (1) = O (n / 2 ^ k) when: n = 2 ^ k.
• Note that at each step m have 3 ^ m splits.
• Now we'll combine all the steps together, using the geometric progression and logarithms rules. In the end, you will get: T(n) = 3T(n/2)+n = 2n^(log3)-2n the calculation

Solution 3

Have a look here at page 60 http://www.cs.columbia.edu/~cs4205/files/CM2.pdf.

And maybe you should have asked here https://math.stackexchange.com/

Solution 4

The problems like this can be solved using Masters theorem.

In your case a = 3, b = 2 and f(n) = n.

So c = log_b(a) = log_2(3), which is bigger than 1, and therefore you fall into the first case. So your complexity is:

O(n^{log_2(3)}) = O(n^{1.58})

View more solutions

Comments

[nat45928]

Thanks for the link, but I'm still lost on how to proceed. I don't get how you can simply the two different bases.

[vaibhavatul47]

In the last line of calculation, you reduced (3/2)^logN to N^log(3/2), IMO this looks wrong.