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.

  • 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
    @J.M. Thanks! For some reason I had never encountered this before.2011-10-30