Solve the recurrence relation: T(n)=T(n/2)+T(n/3)+T(n/4) + n

+8 votes
Solve the recurrence relation: T(n)=T(n/2)+T(n/3)+T(n/4) + n
asked Feb 14 in Divide & Conquer by Amrinder Arora (206 points)

4 Answers

0 votes
 
Best answer

Since we have at least 5 upvotes, I will provide the answer.

Hypothesis: T(n) = O(n^k), where k = log_2(13/6).   That is, log to the base 2 of (13/6).  We can observe that k is slightly larger than 1.  It is approximately 1.115.

Now, to prove it, we simply use mathematical induction.

Hypothesis: T(n) <= c n^k

Base Case: T(1) = 1, so this is true, as long as c >= 1.  (We will actually end up choosing c that is larger than that anyway.)

Induction Hypothesis: Assume T(n) <= c n^k for all n <= m

Inductive Step:

T(m) = T(m/2) + T(m/3) + T(m/4) + m

<= c m^k (1/2^k + 1/3^k + 1/4^k) + m

 = c m^k 0.89 + m

We can make this to be less than equal to cm^k, as long as c > 1/0.11

So, we can choose c = 10.

(You are also allowed to do this as rough calculation before, and then start your entire hypothesis as T(n) <= 10 n^k.)

answered Mar 7 by Amrinder Arora (206 points)
selected Mar 20 by Amrinder Arora
+1 vote

How about to solve it this way?

Because T(n/2)+T(n/3)+T(n/4)<=3T(n/2)

So T(n)=O(3T(n/2)+n)

T(n)=O(n^log23)

answered Mar 7 by zhouce Active (276 points)
It is a good way, but it is not very accurate.  For example, log_2 (3) is 1.58.  While the actual answer is just 1.115, so, quite different.
0 votes

If we have a number A that

(1/2)^A+(1/3)^A+(1/4)^A=1

Solve this equation,

Then (n^A) is our answer.

Proof´╝ÜTn= O(n^A)

Guess Tn<= c(n^A)-n

Tn=n/2+ n/3+ n/4+n <= 

c(n/2)^A-n/2+c(n/3)^A-n/3+c(n/4)^A-n/4+n=

c[(1/2)^A+(1/3)^A+(1/4)^A]*(n^A)-n/12

if (1/2)^A+(1/3)^A+(1/4)^A=1,

Tn<= c(n^A)-n/12<=c(n^A) can be proved

so,

A is the solve of (1/2)^A+(1/3)^A+(1/4)^A=1

A is a real number.

In Mathematica:

Input: Solve[(1/2)^x + (1/3)^x + (1/4)^x == 1, x, Reals]

One Output: {1.08213149814041866081}

answered Feb 16 by shijie Active (276 points)
edited May 9 by shijie
0 votes

Alternate answer:

Hypothesis: T(n) = O(n^k), where k = log_2(13/6).   That is, log to the base 2 of (13/6).  We can observe that k is slightly larger than 1.  It is approximately 1.115.

Now, to prove it, we simply use mathematical induction.

Hypothesis: T(n) <= 10 n^k

Base Case: T(1) = 1, so this is true.

Induction Hypothesis: Assume T(n) <= 10 n^k for all n <= m

Inductive Step:

T(m) = T(m/2) + T(m/3) + T(m/4) + m

<= 10 m^k (1/2^k + 1/3^k + 1/4^k) + m

 = 10 m^k 0.89 + m

 = 8.9 m^k + m

<= 8.9 m^k + m^k  (Since we know that k > 1, so m^k > m)

 <= 10 m^k.

Therefore, by PCMI, T(n) <= 10 n^k for all values of n.

Therefore, T(n) = O(n^k)

[Note that the proof by induction portion depends on actual inequalities and does not use asymptotic notation at all.]

answered Mar 7 by Amrinder Arora (206 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...