- All categories
- Asymptotic Analysis (22)
- D&C (9)
- Greedy (1)
- Dynamic Programming (7)
- Backtracking/DFS/BFS (2)
- Branch & Bound (2)
- Graph Theory (14)
- NP-Completeness (4)

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

+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)

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}

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

...