Solving recurrence relation $T(n) = T(n/3) + T(n/2) + n^3$

Question

Solve the recurrence relation $T(n) = T(n/3) + T(n/2) + n^3$.

Could someone help me with this question here? I have tried the problem using recurrence tree but it starts getting complicated pretty quick. How would one approach to solve such problems?

Answer 1

You are presumably just looking for an asymptotic estimate?

It's usually worth guessing that the solution is asymptotically the same as the inhomogeneous term; in this case

$$ T(n) = \Theta(n^3) $$

and then do the exercise "prove/disprove that this is a solution to the recurrence".

Often this works. When it doesn't, your work often gives you useful information about the problem — e.g. suggesting other guesses you can make.

Answer 2

I can give some pointers,

• The recurrence is dividing the data set in two ways, T(n/3) and T(n/2)

  And the coefficient of both is one, that is, in T(n/3): only one-third of the data is selected to perform the further operation and in T(n/2): half of the data is selected to perform the next operations.

  So, if we consider T(n/3), we'll get lower bound. And if we consider T(n/2) we'll get upper bound.

• Now if you solve T(n) = T(n/3) + T(n/2) + O(1). As in, Binary and Ternary(modify Binary with little if-else) search, a single or more specifically constant amount of operations which does not depends on data size at that level of recurrence tree.

  You will get asymptotic maximum of O(log2(n)), which is just the cost of navigating through the data(or in other words, dividing the problem into sub-problems and then combining them again). Which is the time consumed by your algorithm on n-size data set.

  But for, T(n) = T(n/3) + T(n/2) + O(n^3), it is not same. Here the cost of operation function at each recurrence call(that is, on each sub-problem is, O(n^3)), is much greater than the cost of navigating through the data. And hence the upper Asymptotic bound.

• Now my explanation is little bit convoluted like, i'm explaining to myself ;). I would recommend Introduction to Algorithms - Cormen, Pg - 70. In a gist the basic theme of both(T(n) = T(n/3) + T(n/2) + O(n^3) and T(n) = T(n/3) + T(2n/3) + O(n)) the questions is same.

Plus, there is nothing "complicated" while solving it with recurrence tree, if you look closely the coefficient of the terms take form as in Pascal's triangle.

Edit

Fun fact, the question asked just before your question under recurrence-relation tag is on, Pascal's triangle. Just observed.