0
$\begingroup$

I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering why are we allowed to compute a sum of a polynomial and a set. Why not just teach that for every $n\in\mathbb N$ there is a $f:\mathbb N\to \mathbb N$ such that $f\in \Theta(n)$ and $2n^2+3n+1=2n+f$? Is this a formally correct way to think $\Theta$ notation? Or should I learn some other book to learn O-notations, like J.D. Murray: Asymptotic analysis? Or do I have some misunderstanding that becomes clear if I first learn some book of axiomatic set theory?

$\endgroup$
2
$\begingroup$

The answers and comments by other users here do a good job of explaining how the notation works, so I figure I'll explain why the notation is used this way. The reason for the notation is already evident in your question: writing out the set inclusion explicitly makes it way more verbose.

When you are learning asymptotic notation for the first time, it is helpful to clearly state that $O$, $\Theta$, etc. are not functions and that "equality" does not behave like equality in statements involving these symbols. But when you are an expert in a field reading a hundred-page paper written by other experts in the same field to communicate with their kin, you really don't want to have to read this kind of boilerplate over and over again if you can avoid it.

The purpose of asymptotic notation is to allow the author to state theorems and intermediate steps in an extremely compact fashion. When you read something like $f(n) = 5n^3 + 3n^2 + o(n^2)$, what you are really reading is, "$f(n)$ is equal to $5n^3 + 3n^2$ plus a bunch of junk that neither you nor I have time to care about because it is sufficiently small that its exact value is irrelevant to the correctness of the rest of the argument I am about to present". Writing everything out in terms of statements about sets would obscure the point the author is trying to communicate.

$\endgroup$
1
$\begingroup$

The clearest, most complete, introduction to asymptotics I've yet found is Hildebrand's "Short Course on Asymptotics". Somewhat heavy going, but nailing the concepts down is crucial.

BTW, $2 n^2 + 3 n + 1 = 2 n + \Theta(n)$ is clearly wrong, it presumably was meant to be $2 n^2 + 3 n + 1 = 2 n^2 + \Theta(n)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy