# Formally correct way to define asymptotic notations

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.

• 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)$. Commented Aug 21, 2014 at 20:58
• 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. Commented Aug 21, 2014 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
Commented Aug 21, 2014 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. Commented Aug 22, 2014 at 8:13

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