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

William Lee Irwin III wli at holomorphy.com
Fri Feb 4 09:20:44 EST 2005

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

-- wli

More information about the Haskell-Cafe mailing list