3 ms·

Strictly speaking, yes. O-notation describes the growth of a function as the argument tends to infinity. Formally, the statement "f(x) is O(g(x))" means that th

Strictly speaking, yes. O-notation describes the growth of a function as the argument tends to infinity. Formally, the statement "f(x) is O(g(x))" means that there's some point x_0 such that f(x) is less than a constant factor times g(x) for any x > x_0. This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)). An algorithm can be O of different g(x)s, depending on the properties of the input. For example, the runtime of a naive quicksort implementation (which always chooses the leftmost value as a pivot) is O(n^2) if the input list is sorted, while it has runtime O(n*lg(n)) on average and in the best case (where the pivot is always the median of the section of the list being partitioned).

varjag 16y ago
> This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)). It is not, because constant function has no logarithmic behavior. To distinguish that is the whole point of big-O notation. When you tell someone "this is a O(logn) operation" they do expect log performance. Yes O(c) is strictly under O(n) too, but so what? We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.
- jbapple 16y ago
  > When you tell someone "this is a O(logn) operation" they do expect log performance. If you look in the appendix of your algorithms textbook that explains big-O notation, you will see this is not the actual definition. I'm sorry if my usage confused you, but I was using it in the formal sense of "there exists an N such that there exists a c such that for all m > N, f(m) <= c*g(m)". In your log example, we can choose N = 2 and c = 1. > We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions. For saying "f is doubly-exponential", use Theta. For saying "f is doubly-exponential or smaller", use big-O. http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma...
- aperiodic 16y ago
  > It would be one of those formally correct but practically useless definitions. "Hi, my name is Aperiodic, and I'm... a mathematician." "Hi Aperiodic." "It all started out so easily; you know, a few lemmas with the boys in the evenings. But before I knew it, I was picking up Bourbaki as soon as I got home from work. I would wake up in the mornings, surrounded loose sheets of paper covered in commutative diagrams, without a clear idea of what I did last night..."

varjag 16y ago

> This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)). It is not, because constant function has no logarithmic behavior. To distinguish that is the whole point of big-O notation. When you tell someone "this is a O(logn) operation" they do expect log performance. Yes O(c) is strictly under O(n) too, but so what? We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.

jbapple 16y ago
> When you tell someone "this is a O(logn) operation" they do expect log performance. If you look in the appendix of your algorithms textbook that explains big-O notation, you will see this is not the actual definition. I'm sorry if my usage confused you, but I was using it in the formal sense of "there exists an N such that there exists a c such that for all m > N, f(m) <= c*g(m)". In your log example, we can choose N = 2 and c = 1. > We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions. For saying "f is doubly-exponential", use Theta. For saying "f is doubly-exponential or smaller", use big-O. http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma...
aperiodic 16y ago
> It would be one of those formally correct but practically useless definitions. "Hi, my name is Aperiodic, and I'm... a mathematician." "Hi Aperiodic." "It all started out so easily; you know, a few lemmas with the boys in the evenings. But before I knew it, I was picking up Bourbaki as soon as I got home from work. I would wake up in the mornings, surrounded loose sheets of paper covered in commutative diagrams, without a clear idea of what I did last night..."