Subj : Re: puzzle
To   : comp.programming
From : Ben Bacarisse
Date : Tue Jun 28 2005 07:55 pm

On Tue, 28 Jun 2005 16:19:13 +0000, Richard Harter wrote:

> 	f(x) = O(g(x)) => There exists X and positive C such that for
> all x>X
> 	|f(x)| <= C*|g(x)|
> 
> What this implies is that something that is O(n) also is O(n*n) etc.

You are, of course, quite correct.  I had hoped to finesse this point by
trying to ascibe a meaning to the phrase "this problem is O(f(x))"
which, if it is to mean anything useful, must mean that all algorithms to
solve it are Omega(f(x)).  But I should not have done so without
introducing the less well known Omega notation!

[Omega (also introduced by Knuth in '76) being the lower-bound
equivalent to big-O such that f is Theta(g) iff f is Omega(g) and also O(g).]

Re-reading my rant, I see that I use absurd phrases like "at least O(n^2)"
which, while it may have a colloquial meaning, is almost a mathematical
oxymoron.  The notation is there for a reason and I should have used it.

> We really do want O() to mean "bigger than" because in analysis we often
> have a bound without knowing whether it is the best bound possible.  In
> 1976 Knuth suggested Theta as a notation for being of the same order.  I
> suppose it has become standard but it certainly is cumbersome in
> ordinary text.

They are certainly standard, but not just cumbersome in text.  It is
also fiddly to get the techincalities right to show that, say, the time
complexity of an algorithm is Theta(f(n)) where showing it to be O(f(n))
for the "best possible" f you can think of is usualy easier.

-- 
Ben.

.