Question

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

Answer 1

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.]

As to how we "guess" the number 13/6, let us approach this as:

S(n) = a S(n/b) + n.  We want this to be "similar" (a/b = 13/6) to the given T term, then we solve S using MT, and use the answer as a guess.. [b > 1]

S(n) = 13/6 S (n/2) + n

Answer 2

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)

Comments

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.

Answer 3

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}