1
$\begingroup$

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

  • 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.2011-10-28
  • 0
    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?2011-10-28
  • 0
    There are things between n and n^2. I put in n^k and found a root for 2>k>1.2011-10-28
  • 0
    Yes like nlogn and such. But is my method wrong?2011-10-28
  • 0
    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.2011-10-28
  • 0
    Ah I get what you mean! Thank you!2011-10-28
  • 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?2011-10-28
  • 0
    Prove that A(n)=O(n).2011-10-28

1 Answers 1

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.

  • 0
    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))$.2011-10-28
  • 0
    @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.2011-10-28
  • 0
    +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](http://math.stackexchange.com/q/73643/11619), where a double exponential scale is suggested.2011-10-29
  • 0
    @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.2011-10-29
  • 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... :)2011-10-30
  • 0
    @J.M. Thanks! For some reason I had never encountered this before.2011-10-30