Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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 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
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 8:19

1 Answer 1

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.

share|improve this answer
    
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
    
@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 7: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. Oct 30 '11 at 15:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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