2

I found an algorithm book which tries to define asymptotic notations as sets and then used notations like $n=O(n^2)$. Is there a mathematically correct way to define asymptotic notations like $O(n), \Omega(n), \Theta(n), o(n)$ and $\omega(n)$? And is there an algorithm books that uses notations correctly?

I found something about http://www.artofproblemsolving.com/Forum/viewtopic.php?f=296&t=31517&start=20 but the problem is that I don't know rigorous definitions of class and set and difference of those so I can't say if it is a correct approach to formalize the $O$ notation.

computerenthusiastic
  • 33
  • Things like $n = O(n^2)$ are a slight abuse of notation, since it implies that $O(n^2) = n$, which doesn't make sense. Indeed, some people prefer using notation like $n \in O(n^2)$. – Adriano Aug 21 '14 at 20:58
  • 1
    There are different definitions of big-O notation. In some fields (e.g., computer science), $O(\cdot)$ is a set of functions with a certain bound on their runtime. In other fields (e.g., analysis), $O(\cdot)$ represents a single function defined implicitly by the equation it appears in but is otherwise unspecified. Neither convention is flawless; one has to get used to how it can correctly be manipulated. – Greg Martin Aug 21 '14 at 21:10
  • @GregMartin It seems you are ascribing to different fields the difference between a definition and the use of the notion it defines. Indeed, $O(n)$ is some precisely defined class of sequences. But I want to be able to write that $n^2+42n+17=n^2+O(n)$ without believing one second that $O(n)$ is a single sequence. – Did Aug 21 '14 at 21:50
  • I can only say that in my experience, some people define $O(n)$ to be a class of sequences, others use it to mean a specific sequence. You can use whichever is convenient and happy for you. – Greg Martin Aug 22 '14 at 08:13

1 Answers1

0

You should probably check this wiki page

$n=O(n^2)$ is mathematically correct because $\frac{n}{n^2}=\frac{1}{n} < 1$. It is also true that $n=o(n^2)$ as $\lim_{n\rightarrow +\infty} |\frac{n}{n^2}|=0$

I don't have any reference on the subject, but the books I've seen usually use the notations properly, even if they don't go into much details about what the symbol really means. You just need to remember how to compare powers, ln and exp and you'll be fine 99% of the time.

Matt B.
  • 1,246