1

$$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.

J. M. ain't a mathematician
  • 75,051
Laciel
  • 221
  • 2
    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 03: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 04: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 04:08
  • Yes like nlogn and such. But is my method wrong? – Laciel Oct 28 '11 at 04:12
  • You have found a solution that grows with linear time. But if there is a solution that grows faster, it will dominate eventually. To prove O(n) you have to prove there is nothing greater. I haven't proven mine is right, just that it is >O(n). I tried r^n and didn't find a solution, but there might be another one lurking out there. – Ross Millikan Oct 28 '11 at 04:16
  • Ah I get what you mean! Thank you! – Laciel Oct 28 '11 at 04:18
  • 1
    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 08:19
  • Prove that A(n)=O(n). – Laciel Oct 28 '11 at 14:35

1 Answers1

3

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.

Christian Blatter
  • 226,825
  • 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))$. –  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 06:51
  • @All: What's the English translation for 'Ansatz' in this context? If I literally translate the Finnish term it would be something like a 'trial solution' or some such. – Jyrki Lahtonen Oct 29 '11 at 07:18
  • 1
    @Jyrki: "ansatz" is actually a fine term for English use; mathematicians and physicists have appropriated the term and have used it extensively in English communication... :) – J. M. ain't a mathematician Oct 30 '11 at 15:25
  • @J.M. Thanks! For some reason I had never encountered this before. – Jyrki Lahtonen Oct 30 '11 at 16:57