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