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

[Dylan Thurston]

On Fri, Feb 04, 2005 at 05:47:20AM -0800, William Lee Irwin III wrote:
> On Fri, Jan 28, 2005 at 08:16:59PM +0100, Henning Thielemann wrote:
> >> But what do you mean with 1/O(n^2) ? O(f) is defined as the set of
> >> functions bounded to the upper by f.  So 1/O(f) has no meaning at the
> >> first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x)
> >> (i.e. lifting from scalar reciprocal to the reciprocal of a function) and
> >> then as lifting from a reciprocal of a function to the reciprocal of each
> >> function of a set. Do you mean that?
> 
> On Thu, Feb 03, 2005 at 08:16:49PM -0500, 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.
> 
> Careful, 2^x is monotone increasing; 1/x is monotone decreasing. I
> said 1/O(n^2) is Omega(1/n^2) for a good reason. Inequalities are
> reversed by monotone decreasing functions.

Sorry, isn't that what I said?  Am I confused?

> Also, you're in a bit of trouble wrt. 2^(O(n)). O(2^n) is something
> rather different. O(2^n) has |f(n)| <= K*|2^n| but 2^(O(n)) is 2^|f(n)|
> where |f(n)| <= K*|n|. If K >= 1/log(2) is sharp then then we have
> 2^|f(n)| >= e^|n| \in omega(2^n).

I don't follow the last sentence, but yes, O(2^n) and 2^(O(n)) are
different.  In particular 2^(O(n)) and (e.g.) 3^(O(n)) are the same.

Peace,
	Dylan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20050205/b694ea7d/attachment.bin