Re: deques, deques, and dequeues

In article <1178849205.271520.199410@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Keith H Duggar <duggar@xxxxxxxxxxxx> wrote:

Thus the O-notation says nothing about the algorithm it
says something about a particular function, or statistic
if you will, of the algorithm. This is why the types of
statements we see are such:

Earlier in this thread it was made clear that the comments were being
made about time complexity of an algorithm, not about the algorithm
itself.


"The worst case running time is O(n*log(n)) ..."
"The expected running time is O(n) ..."
"The best case space is O(log(n)) but the worst case
space is a staggering O(n^3) ..."

etc

Thus O-notation is not "by definition worst case". It can
apply to any "case" ie any statistic of an algorithm and
which one is being described must be stated.

And it was. The context got lost, but it had been clearly established.


If you say a function of n is O(n) the implication is that
as n grows quite large, the function's output will tend to
approximate its input.

What does that last phrase "the function's output will tend
to approximate its input" mean above?

It means exactly what it says. What do you consider ambiguous about it?

it's less problematic than the prior post talking about
"O(1) on average."

No that is a perfectly legitimate statement.

It's not, because Big-O notation is intended to describe the behavior of
the function as its argument grows very large. I'm not aware of any
sensible meaning of the tacked-on "on average."

I would dare to
say any undergraduate taking an algorithms course (especially
a randomized algorithms course) would hear their professor
make the same statement.

This one didn't when he was an undergraduate. Neither in math nor
computer science courses, of which I took many.

G
.

Relevant Pages