3

Is there a difference between the method to find a big-O function and the method to find the best big-O function. Take for example the following function:

$f(n) = 1 + 2 + 3 + ... + n$

It is easy to show that $f(n)$ is $\mathcal{O}(n^2)$ like this:

$1 + 2 + 3 + ... + n \leq n + n + n + ... + n = n \cdot n = n^2$ for $n \geq 1$

Such that the witnesses are $C=1$ and $k=1$

But how do I know if this is the best big-O function? I need to know how to do this for more complex functions than the one shown.

Julia
  • 496
  • In this case, you are not looking for big-Oh notations -- the Landau notation ("equivalent," denoted $f\sim g$ for (roughly) $\frac{f}{g}\to 1$) would be more suited. – Clement C. Jun 30 '15 at 13:12
  • @ClementC. Ok, I understand what you're saying, but the question asks specifically for "best" big-O. Is "best" big-O the same as "equivalent" then? – Julia Jun 30 '15 at 13:14
  • Well, "best Big-Oh" basically has no meaning -- the "big-Oh" notation is designed to ignore the constants. I believe what you are looking for is closer to an equivalent, although a more rigorous and precise notion would be $\lim\sup \frac{f}{g}$ (instead of $f=O(g)$). – Clement C. Jun 30 '15 at 13:16
  • I'd call that "asymptotic", not "equivalent". – Gerry Myerson Jun 30 '15 at 13:17
  • Perhaps by "best big-$O$" you mean $\Theta$ ? – lhf Jun 30 '15 at 13:17
  • @lhf: if I understand the question, this is all about the constants (i.e., in the example, getting $C=1/2$). But I may be wrong. – Clement C. Jun 30 '15 at 13:19
  • @lhf That makes sense. The question that I found online asks for best big-O and then gives a list of options to choose from. Not a very clear question in my opinion. I think $\Theta$ is right. – Julia Jun 30 '15 at 13:19
  • @ClementC, it may be, yes. – lhf Jun 30 '15 at 13:21
  • @Julia: if the goal is to find $g(n)$ such that $f(n)=O(g(n))$ and $g(n)=O(f(n))$, this is the $\Theta(\cdot)$ notation. If it is about the best constant possible, then i'd say it is the $\lim\sup$ above. Where is the question from? – Clement C. Jun 30 '15 at 13:22

1 Answers1

5

We have $f(n)=\frac{n(n+1)}{2} \ge \frac{n^2}{2}$ and so $f$ is $\Omega(n^2)$.

Since $f$ is $O(n^2)$, we conclude that $f$ is $\Theta(n^2)$.

It is in this sense that $n^2$ is the "best" function for $f$, in the asymptotic sense, when constants do not matter.

On the other hand, $f(n) \sim \frac{n^2}{2}$, and so $\frac{n^2}{2}$ is also the best function for $f$, in the asymptotic sense, when constants matter.

lhf
  • 216,483