Problem Detail: 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?
Asked By : thyago stall
Answered By : Yuval Filmus
The $sim$ notation is similar to the more conventional $Theta$ notation. There are two main differences between $sim$ and $O$:
- $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$. - $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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52776
