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

         T(n)            -&gt; Cost: n
    /     |    \
T(n/2)  T(n/3)  T(n/6)   -&gt; total cost: n/2 + n/3 + n/6 = n
   .
   .
  T(1) ---------------&gt;  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 &gt; 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}) &lt; 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})$.