[Haskell-cafe] Re: mathematical notation and functional programming

[William Lee Irwin III]

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