Timeline for Difference between the tilde and big-O notations
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2020 at 17:40 | comment | added | Yuval Filmus | 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:39 | comment | added | Archer | Could you elaborate on the difference between $\sim$ and $\Theta$? | |
| Feb 7, 2016 at 14:57 | comment | added | Yuval Filmus | I disagree, but we can leave the discussion to another occasion. | |
| Feb 7, 2016 at 13:46 | comment | added | Raphael | "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:44 | comment | added | Raphael | 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 6, 2016 at 21:24 | vote | accept | thyago stall | ||
| Feb 6, 2016 at 21:18 | history | answered | Yuval Filmus | CC BY-SA 3.0 |