# Difference between the tilde and big-O notations [duplicate]

Robert Sedgewick, at his Algorithms - Part 1 course in Coursera, states that people usually misunderstand the big-O notation when using it to show the order of growth of algorithms. Instead, he advocates for the tilde notation.

I understand the big-O is an upper bound for certain problem at certain condition.

What is the difference between the tilde and big-O notations?

• Perhaps you should ask Sedgewick. One tilde $\sim$ notation which is often used in other areas is identical to our $\Theta$. Feb 6, 2016 at 20:22
• This question is improperly tagged as a duplicate but see here for an easy answer: youtu.be/yz850zzjrHQ?t=323 Oct 5, 2020 at 13:29
• The difference is quite delicate, prof. Sedgewick gave def. of tilde explicitly: $f(x) \sim g(x)$ means $\lim_{x\to\infty}\ \frac{f(x)}{g(x)} = 1$. For def. of $\mathcal{O}$ (big-oh), $f=\mathcal{O}(g)$ means $\frac{f(x)}{g(x)} \le M$ for some $M\gt 0$, as ${x\to\infty}$. From there, one can see $\sim$ measures the complexity more precise than $\mathcal{O}$ since for $f(x)=x, g(x)=x^{100}$ we have $f=\mathcal{O}(g)$. Note that both definitions require $f(x), g(x) \gt 0$ as $x\to\infty$, but in the context of algorithm analysis, this is obvious. Apr 21 at 5:48

The $\sim$ notation is similar to the more conventional $\Theta$ notation. There are two main differences between $\sim$ and $O$:

1. $O$ only provides an upper bounds, while $\sim$ is simultaneously an upper bound and a lower bound. When we say that the running time of an algorithm is $O(n^2)$, this doesn't preclude the possibility that it is $O(n)$. In contrast, if the running time is $\sim n^2$ then it cannot be $\sim n$.
Another notation with these properties is $\Theta$.

2. $O$ only holds up to a constant: $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C > 0$ (and large enough $n$). In contrast, for $\sim$ the implied constant is always $1$: if $f \sim g$ then $f/g \to 1$. This contrasts with $\Theta$ in which the implied constant is arbitrary, and indeed there could be different constants for the lower and upper bounds.

Exact constants are impractical in general, for many reasons: they are machine dependent, hard to compute, and could fluctuate depending on $n$. The first problem can be mitigating by measuring some proxy for the actual time complexity, such as the number of comparisons in a sorting algorithm.

Sampling the course, it seems they are using $\Theta$, but call it order of growth.

• Sedgewick does in fact advocate using $\sim$ or even stronger relations, i.e. to fix as many constant factors and lower-order terms as possible. Feb 7, 2016 at 13:44
• "Exact constants are impractical in general, for many reasons: they are machine dependent, hard to compute, and could fluctuate depending on n." -- 1) In theory, we never analyse "time", anyway. 2) Constant factors are quite often very feasible to compute -- it's just a cultural thing of laziness and not knowing the tools. 3) Constants don't fluctuate. Lower-order terms can, of course, exist, and can be found. Feb 7, 2016 at 13:46
• I disagree, but we can leave the discussion to another occasion. Feb 7, 2016 at 14:57
• Could you elaborate on the difference between $\sim$ and $\Theta$? May 13, 2020 at 17:39
• We have $f \sim g$ if $f(n)/g(n)$ tends to $1$ in the limit. We have $f = \Theta(g)$ if there exist $c_1,c_2 > 0$ such that $c_1 \leq f(n)/g(n) \leq c_2$ for all $n$. May 13, 2020 at 17:40

The definitions are that $$f(n) = O(g(n))$$ if for some constant $$c > 0$$ and $$N_0$$, you have that $$f(n) \le c g(n)$$ whenever $$n \ge N_0$$. I.e., $$g$$ gives an upper bound (within a not specified constant). Similar is $$f(n) = \Omega(g(n))$$, for other constants $$c'> 0, N_0'$$ you have $$f(n) \ge c' g(n)$$ whenever $$n \ge N_0'$$. I.e., a lower bound (within a constant). It is said that $$f(n) = \Theta(g(n))$$ if both the above are satisfied.

Note that e.g. $$n^2 = O(n^3)$$, and $$n^2 = \Omega(n)$$, while $$200 n^{1 + 1/n} = \Theta(n)$$.

The definition of $$f(n) \sim g(n)$$ is more demanding: it is that:

$$\lim_{n \to \infty} \frac{g(n)}{f(n)} = 1$$

No arbitrary constants, the functions grow together. In this sense, it is similar to $$\Theta$$, but sharper.