Question

Solve this recurrence relation: T(n) = T(n/3) + T(n/5) + T(n/6) + n

Answer 1

Preliminary Work, to build our hypothesis

T(n) = T(n/3) + T(n/5) + T(n/6) + n

We know that n/3 + n/5 + n/6 = n (10/30 + 6/30 + 5/30) = n 21/30 = 7n/10.

So, we could write this recurrence as similar to: R(n) = R(7n/10) + n

n represents 3/10 part of the overall work.  So, it APPEARS that T(n) = 10n/3.  By "Appears" we mean that this is not a proof, this is just an exercise to reach a good guess.  Proof is what comes next.

Proof by Induction

Our hypothesis is: T(s) <= 10s/3  for all s

Base Case

T(1) = C, this works, as long as C <= 10/3.  (Sure, we say that it is.)

Induction Hypothesis

Assume that T(s) <= 10s/3 for all s <= n-1

Inductive Step

We now need to prove the hypothesis for n.

So, for n, T(n) = T(n/3) + T(n/5) + T(n/6) + n

Using Induction Hypothesis (which applies for cases n/3, n/5 and n/6), we have that:

T(n) <= 10(n/3)/3 + 10 (n/5)/3 + 10(n/6)/3 + n

      = n (10/9 + 10/15 + 10/18 + 1)

     = n 10/3

Therefore, T(n) <= 10n/3 for all n.

Therefore, by PMI, our hypothesis is valid.

Now, we can go back to Asymptotic notation, and conclude that:

T(n) = O(n).