Timeline for Analysis of very simple algorithm
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2015 at 22:18 | comment | added | Joey Eremondi | Sorry, the O represents the fact that it's an upper bound. The function inside is the "order" of the upper bound, i.e. how big is it i.e. drop the constants and smaller terms. The point I was trying to make is that $O(2n) = O(1.5n) = O(n)$, you can increase the constants without losing anything. And you can increase the inner function without losing anything, though your bound is no longer tight. The above code runs in $O(n^2)$ time but not $\Theta(n^2)$ time. | |
| Mar 12, 2015 at 22:00 | comment | added | David Richerby | $O(-)$ isn't an upper bound, as you show by one of your examples. $2n\in O(n)$ but $n$ is not an upper bound for $2n$. | |
| Mar 12, 2015 at 21:32 | history | answered | Joey Eremondi | CC BY-SA 3.0 |