Forgive me if I am new, I am trying to learn how to solve recurrences.

I have the following recurrence:

$$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 \text{ if } n>0$$

Now from my understanding is that I am not able to use the following methods.

  1. Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)
  2. Tree Method (because of the $\frac{1}{2} T$, you cannot have a node of $\frac{1}{2}$), please correct me if I am wrong.

So which leaves me with the following method:

Only the substitution method, but what I don't understand that is the fact that for the substitution method, you have to guess for the $f(n)$ to substitute into the recurrence.

So my question is, how does one select the correct $f(n)$ to substitute?

  • $\begingroup$ I just made some basic edits (just markup, no content change), please check that I didn't mess anything up in the recurrence. $\endgroup$ – Luke Mathieson Sep 23 '13 at 3:12
  • $\begingroup$ @LukeMathieson Thanks! I should learn how to fix that! $\endgroup$ – Joh Steward Sep 23 '13 at 3:31
  • $\begingroup$ Note that "substitution method" actually is an induction proof. Guessing a correct bound is exactly that: guessing. We have compiled a reference question on solving recurrences that should provide you with a rich toolbox; if you can't apply anything, edit your question with an attempt and specific questions. $\endgroup$ – Raphael Sep 23 '13 at 7:25
  • $\begingroup$ @Raphael, i understand that, we are guessing for upper and lower bound, what I am confused about is how to guess for an upper and lower bounce in which it is tight $\endgroup$ – Joh Steward Sep 23 '13 at 12:42
  • $\begingroup$ @JohSteward You will almost never guess tight bounds (if you are after $\Theta$-bounds). You can, for instance, try $c_1 = \frac{1}{2^{100}}$ and $c_2 = 2^{100}$; that'll work just as well as $c_1=3$ and $c_2=4$. The additional information is lost as soon as you say $\Theta(\dots)$, anyway. (Disclaimer: finding tight bounds is interesting in itself.) $\endgroup$ – Raphael Sep 23 '13 at 17:23

Use the Akra-Bazzi theorem. Let $p$ be the solution to $2\cdot(1/3)^p + (1/2)\cdot(2/3)^p= 1$, namely $p = 1$. Compute $$ S(n) = \int_1^n \frac{x^2}{x^{p+1}} \, dx = n-1= \Theta(n). $$ Then $T(n) = \Theta(x^p S(n)) = \Theta(n^2)$.

  • $\begingroup$ interesting. I've never heard of this (as I am still learning) Thanks! $\endgroup$ – Joh Steward Sep 23 '13 at 12:45

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