"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..."
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_Bachma...
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.