Re:Show HN: New Lisp data structure
by jbapple on Thursday December 02, 2010 @10:54AM
(#1962452)
> 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.
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...