4 Feb
2005
4 Feb
'05
2:20 p.m.
On Thu, 3 Feb 2005, Dylan Thurston wrote:
I think this is the only reasonable generalization from the established usage of, e.g., 2^(O(n)). In practice, this means that 1/O(n^2) is the set of functions asymptotically bounded below by 1/kn^2 for some k.
On Fri, Feb 04, 2005 at 03:08:51PM +0100, Henning Thielemann wrote:
I haven't yet seen the expression 2^(O(n)). I would interpret it as lifting (\x -> 2^x) to sets of functions, then applying it to the function set O(\n -> n). But I assume that this set can't be expressed by an O set.
You're right, it can't be expressed as O(g(n)) for any g(n). For that matter, and neither can sech(O(n^2)) be expressed as Omega(g(n)) for any g(n). -- wli