0
$\begingroup$

I have some problems of understanding asymptotic definitions of the growth of functions. Namely, I saw from the algorithm book of mine that $O(g(n))=\{f(n):$ there exist a positive constants $c$ and $n_0$ such that $0\leq f(n)\leq cg(n)$ for all $n\geq n_0\}$. But in https://artofproblemsolving.com/community/c7h31517 I saw a more rigorous definition:

Given a positive $ g$ defined in a punctured neighborhood of $ x_0$, denote by $ O_{x_0}(g)$ the class of all functions $ f$ such that the ratio $ f/g$ is bounded in some punctured neighbourhood of $ x_0$.

Here, I think class means a set.

So I think it would be nice to learn similar rigorous definitions for other asymptotic notations

$\theta(g(n))=\{f(n):$ there exist positive constants $c_1,c_2,$ and $n_0$ such that $0\leq c_1g(n)\leq f(n)\leq c_2g(n)$ for all $n\geq n_0 \}$,

$\Omega(g(n))=\{f(n):$ there exist positive constants $c$ and $n_0$ such that $0\leq cg(n)\leq f(n)$ for all $n\geq n_0$,

$o(g(n))=\{f(n):$ for any positive constant $c>0$, there exists a constant $n_0>0$ such that $0\leq f(n)<cg(n)$ for all $n\geq n_0\}$

$\omega(g(n))=\{f(n):$ for any positive constant $c>0$, there exists a constant $n_0>0$ such that $0\leq cg(n)<f(n)$ for all $n\geq n_0\}$

Also, in my book those sets are used in a weird way like $e^x=1+x+\theta(x^2)$.

So could anyone define rigorously the asymptotic notations $\theta$, $\Omega$, $o$ and $\omega$ and give some guide how to use them in a formal way rather than using notations like $e^x=1+x+\theta(x^2)$? Also, does it give some extra information if we use the notation $O_n(g(n))$ rather than $O(g(n))$?

$\endgroup$
  • $\begingroup$ check the definition here. The definition that you had linked is not more rigorous or general than the definition of wikipedia. $\endgroup$ – Masacroso Nov 25 '17 at 14:24
  • 1
    $\begingroup$ The ‘more rigourous’ definition you cite, though rather intuitive, is not so rigourous as you think: it does not take into account that $g(x)$ might be $0$ at points nearer and nearer to $x_0$. The truly rigourous definition is the first, provided you add absolute values (in which case, the $0\le$ part in superfluous). $\endgroup$ – Bernard Nov 25 '17 at 14:24
  • $\begingroup$ @Bernard Is $f(x)/g(x)$ bounded if $g(x)=0$? $\endgroup$ – Jaakko Seppälä Nov 25 '17 at 20:03
  • $\begingroup$ No, unless perhaps if $f(x)=0$. That's why the first definition is better. $\endgroup$ – Bernard Nov 25 '17 at 20:24
  • $\begingroup$ @user2219896 I've added a reference in my answer. $\endgroup$ – user8469759 Nov 27 '17 at 12:41
1
$\begingroup$

I recognize the notation you're using, that's given in "Introduction to Algorithms". The point of that notation is to denote a set of functions that has some specific properties, without writing the exact function. The notation is not only used in computer science but also in analytic number theory, mathematical physics etc.

In general the idea beyond that notation is to provide tools that provide solutions to problems that are maybe not exact, but still meaning ull.

With reference to $e^x$, we now that for all $x$ we can write the Taylor series

$$ e^x = 1 + x + \frac{x^2}{2} + ... + \frac{x^k}{k!} + ... $$

We we know we are studying the function in a neighbour of $0$ we can write

$$ e^x = 1 + x + o(x) $$

However $o(x)$ tells you that when you put an $x$ close to $0$ the error term get's closer and closer to $0$, as $x \to 0$. Hence the information is "local", namely it tells you how $e^x$ get's similar to $1+x$ when you approach $0$. For something more "global" we can use $\theta$ notation, but we need to find the class of function. Observe that when $\lvert x \rvert < 1$ we have $$ 1+x \leq e^x \leq 1 + x + x^2 \Rightarrow 0 \leq e^x-1-x \leq x^2 $$ Therefore according to the definition we have $c_1=0,c_2=1$ and therefore $$ e^x - 1 - x = \theta(x) \Rightarrow e^x = 1+x+\theta(x^2) $$

Now compare the the information provided by the two

$$ \begin{array}{ll} e^x = 1 + x + o(x) & (1)\\ e^x = 1 + x + \theta(x^2) & (2) \end{array} $$

And to understand the information that $o(x)$ and $\theta(x)$ provide observe that if $g(x) = \theta(x^2)$ for $x\in [a,b], a < 0 < b$ then $g(x) = o(x)$ when $x \to 0$. The proof is easy since

$$ c_1 x \leq \frac{g(x)}{x} \leq c_2x \Rightarrow \frac{g(x)}{x} \to 0 \Rightarrow g(x) = o(x), $$ The converse result isn't true instead, therefore the set $\theta(x) \subset o(x)$ and therefore between $(1)$ and $(2)$ the second one is "more accurate", because we have more information on the error term.

Update:

This is a good reference for asymptotic analysis, unless you're looking for something specific.

$\endgroup$
  • $\begingroup$ Thanks! Is that book rigorous in sense that it does not use things like $O(f(n))+g(n)$ where $O(f(n))$ is a set and $g(n)$ is a value of $g$ at the point $n$? $\endgroup$ – Jaakko Seppälä Nov 28 '17 at 19:39
  • $\begingroup$ Yep, or the algorithms book i mentioned from CLSR $\endgroup$ – user8469759 Nov 28 '17 at 19:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.