# Time complexity described by recurrence relation

I need to find the time complexity described by the following recurrence relation.

$$T(n) = T(n/2) + T(n/3) + T(n/6) + n$$

$$T(1) = \Theta(1)$$

The solution must be something like $$T(n) = \Theta(f(n))$$.

Obviously the standard form of the master theorem can't help me and any other special cases that I have found weren't useful.

• Since $T(n/2) + T(n/3) + T(n/6) = 3O(n/2)$ then you can find an upper bound for that. Oct 25 '19 at 19:22
• Use the Akra-Bazzi theorem. Oct 26 '19 at 10:42

If we draw recurrence tree for this relation than it would be something like following:

         T(n)            -> Cost: n
/     |    \
T(n/2)  T(n/3)  T(n/6)   -> total cost: n/2 + n/3 + n/6 = n
.
.
T(1) --------------->  highest depth which is about lg(n).


So, there are $$lg(n)$$ levels and every level has at least cost $$n$$ so $$T(n) = \mathcal{O}(n\lg{n})$$.

Now let's conjecture that $$T(n) = \Omega(n\lg{n})$$ and try to prove it.

We will prove this by induction.

Let's assume that $$T(n) \ge c.n\lg{n}$$ for some $$c > 0$$.

$$T(n+1) = T(\frac{n+1}{2}) + T(\frac{n+1}{3}) + T(\frac{n+1}{6}) + n+1$$

$$\therefore T(n+1) \ge c.\frac{n+1}{2}.\lg{\frac{n+1}{2}} + c.\frac{n+1}{3}.\lg{\frac{n+1}{3}} + c.\frac{n+1}{6}.\lg{\frac{n+1}{6}} + n+1$$

$$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{2}}{2} + \frac{\lg{3}}{3} + \frac{\lg{6}}{6})$$

$$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{432}}{6}))$$

$$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} \space \space \space$$

$$[\because (n+1 - c.(n+1)(\frac{\lg{432}}{6}) < 0, \space \text{for } c\ge 1]$$

Hence, we have proved that $$T(n) = \Omega(n\lg{n})$$ but we also have $$T(n) = \mathcal{O}(n\lg(n))$$.

So, that implies $$T(n) = \Theta(n\lg{n})$$.