# Recurrence Problem

$$A(n) = A(n/3) + A(n/2) + A(2n/3) + O(n)$$

So I am trying to solve this equation. I let $A(n) = O(n)$. I then solved the equation this way:

$$n/3 + n/2 + 2n/3 + kn,$$ which can simplify to $3n/2 + kn$, which is $cn$, where $k$ and $c$ are some constants.

Is this the right way to do this? Thank you.

-
Isn't letting A(n)=O(n) assuming what you hope to prove? If you assume something greater than O(n) you can argue that the O(n) doesn't matter too much. –  Ross Millikan Oct 28 '11 at 3:45
I don't really understand what you mean. So if I use O(n^2) and get it to cn^2 then it would mean I am right. But because I can't show that am I not right using O(n) as a good guess? –  Laciel Oct 28 '11 at 4:01
There are things between n and n^2. I put in n^k and found a root for 2>k>1. –  Ross Millikan Oct 28 '11 at 4:08
Yes like nlogn and such. But is my method wrong? –  Laciel Oct 28 '11 at 4:12
Is $n\to O(n)$ a given function and you want to solve for $n\to A(n)$, or is your $O$ a Landau symbol and you want to prove that, given this equation, one has $A(n)=O(n)$ also, or what? –  Christian Blatter Oct 28 '11 at 8:19

Write $A(n):=n f(n)$. Then the new unknown function $f$ would have to satisfy $$f(n)={1\over3}f\Bigl({n\over3}\Bigr)+{1\over2}f\Bigl({n\over2}\Bigr)+ {2\over3}f\Bigl({2n\over3}\Bigr)+O(1)\qquad(n\to\infty)\ .$$ To get a counterexample to the OP's conjecture we look for a function $f$ satisfying the exact equation $$f(n)={1\over3}f\Bigl({n\over3}\Bigr)+{1\over2}f\Bigl({n\over2}\Bigr)+ {2\over3}f\Bigl({2n\over3}\Bigr)\qquad (n>0)\ .$$ The "Ansatz" $f(n):=n^\alpha$ for an $\alpha$ to be determined results in the equation $$1\ =\ {1\over3}\Bigl({1\over3}\Bigr)^\alpha+{1\over2}\Bigl({1\over2}\Bigr)^\alpha+{2\over3}\Bigl({2\over3}\Bigr)^\alpha\ =:p(\alpha)$$ for the exponent $\alpha$. Plotting $\alpha\mapsto p(\alpha)$ one sees that this equation has a solution $\alpha_0\doteq 0.640625>0$.
This shows that the function $A(n)\ :=\ n^{1+\alpha_0}$ is a function that satisfies the given estimate, but is not $O(n)$ $\ (n\to\infty)$.
${\bf Edit:}\$ Of course one could have started right away with the "Ansatz" $A(n):=n^\beta$ for a $\beta$ to be determined.
What is your motivation for the ansatz $f(n) = n^{\alpha}$? The reason why I am asking is, for instance, if $f(n) = f(n/2) + O(1)$ and if I do the ansatz you suggest, I would get $f(n) = O(1)$. However, the answer is $f(n) = O(\log(n))$. –  user17762 Oct 28 '11 at 19:58
@Sivaram Ambikasaran: Looking at the functional equation for $f$ I thought that this might be a useful "Ansatz", and I succeeded. In your example the "characteristic equation" $1=p(\alpha)$ leads to the exact solution $f(n)=$const. –  Christian Blatter Oct 28 '11 at 21:09
+1 @Sivaram: Undoubtedly you know how constant displacements in a recurrence relation (such as Fibonacci) suggest an Ansatz of the form $r^n$. If we make the substitution $n=e^x$, and write $f(x)=A(e^x)$ then the homogeneous version of this recurrence relation reads $$f(x)=\frac13\;f(x-\ln3)+\frac12\;f(x-\ln2)+\frac23\;f(x+\ln2-\ln3).$$ So the natural Ansatz $f(x)=r^x$ of the logaritmic parameter $x$ turns into the Ansatz $A(n)=n^{\ln r}$ for the 'exponential' parameter $n$. See also this recurrence, where a double exponential scale is suggested. –  Jyrki Lahtonen Oct 29 '11 at 6:51