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.

  • $\begingroup$ Since $T(n/2) + T(n/3) + T(n/6) = 3O(n/2)$ then you can find an upper bound for that. $\endgroup$
    – aminrd
    Oct 25 '19 at 19:22
  • 1
    $\begingroup$ Use the Akra-Bazzi theorem. $\endgroup$ 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})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.