> 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

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