[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
g(n).
-- wli
More information about the Haskell-Cafe
mailing list