>I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios...
I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant:
>A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.
Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.
No it doesn't. You can talk about upper bounds on average case running time. The function under consideration can be any function, best case, worst case, average case, or any other function.
O-notation is used to represent "asymptotic upper bound" on any function. (Omega-notation for lower bounds, Big Theta for simultaneous lower and upper bounds and so on, on any function).
The upper or lower bounds of functions have nothing to do with the "case-iness" (best/worst/average running times etc) of algorithm running times.
The "meaning" of the function (or for that matter the argument "n"), is completely orthogonal to its bounds.
O(n) by itself does not say anything about what the function represents. The function does not have to be about algorithms.
E.g: It could represent the error between an approximation and actual calculated value. You can use O notation to bound such functions, to state the upper bounds on the rate of growth of the error of an approximation. (Gilbert Strang uses O notation thus in his book "Calculus" for example).
As another example, Knuth applies this notation to dozens of non-algorithm-running-time functions in Chapter 9 of Concrete Mathematics.
Even when using such notation to discuss algorithm running times you really have to say O(n log_n) worst case (or best case or average case) running time for e.g, if you want to be clear.
Thus (for example)from Cormen et al's "Introduction to Algorithms" book, emphasis mine (section 3.1 for anyone interested),
"The Big_Theta(n^2) bound on the worst case running time of insertion sort does not imply a Big_Theta(n^2) bound on the running time of the insertion sort on every input.... when the input is already sorted insertion sort runs in Big_Theta(n) time"
Big-Theta is applied to both best case and worst case running time functions in the above paragraph and the author clearly specifies what he is applying the bound to in each case.
iow btilly is right (about how O notation can be used to represent any function, not just worst case running time functions) and you are wrong (when you say "Upper Bound implies worst case" ). As btilly states, this is a common misconception.
Another common abuse of the notation is to use Big-Oh-notation when Big-Theta is intended.
>No it doesn't. You can talk about upper bounds on average case running time.
Hmm. At first read I agreed with this, but now I don't again. A bound is a theoretical limit. If certain inputs to a function cause it to exceed your "bound" then your "bound" isn't a bound.
I do now agree that "big O" applies to average case - not that I ever intended to deny that average case analysis is a thing; it was just a question of terminology. I think the way to resolve what btilly said with the Wikipedia quote I gave is that the "usually" in "big O notation usually only provides an upper bound" gives rise to the common misconception.
>The function under consideration can be any function, best case, worst case, average case, or any other function.
Could you clarify this? "Average case" describes a class of inputs, not a function. Perhaps I'm just experiencing a parsing error.
">No it doesn't. You can talk about upper bounds on average case running time.
Hmm. At first read I agreed with this, but now I don't again."
You should really just read some textbooks (not being patronizing, just saying that explaining this whole thing from scratch on HN takes too much space and time).
Average Case bounds are used in algorithm analysis.
E.g Lemma 5.2 from Cormen et al's "Algorithms"
"Assuming that the the candidates are presented in a random order, algorithm Hire-Assistant has an average case total hiring cost of O(c ln n)"
Hmm that seems to be an upper bound (hence the O) on an average case. Cormen knows something you don't. ;-)
Earlier in the chapter "Thus we are, in effect averaging the running time over all possible inputs. When reporting such a running time, we will refer to it as the average case running time".
Thus, irrespective of your "agreement", stating the bounds on an average case [whatever] is valid. Sure you have to define what "average" is. In the statement "average case" is defined as a "random order of presentation", iow as a probability distribution represented by a Random variable. Iow, the distribution of the input is a part of the definition, but the bounds are still on a function.
Which brings me to
">The function under consideration can be any function, best case, worst case, average case, or any other function.
Could you clarify this? "Average case" describes a class of inputs, not a function. Perhaps I'm just experiencing a parsing error."
You are being pedantic here . In the very first sentence I said (emphasis new) "You can talk about upper bounds on average case running time."
So yes, A mapping of n to average_running_time_with_n_inputs is a function, often a reccurrence. The definition of average case just constrains the n inputs somehow. It doesn't change the meaning of "bound". And as shown above, from Cormen, (and stated by btilly above) "average case running time of operation foo is O(blah)" is perfectly valid.
Strictly speaking, The Oh notation on the RHS of an "equation" shouldn't be using the equal to sign and should be using an "element of" sign from Set Theory and the terms on both sides are really sets and so on. All this is explained in most good texts.
I also suspect you learned O(n) strictly through algorithms (and not math) and maybe (just guessing here) that's why you are confused about how the various terms map to this or that aspect of algorithms.( I quote you from your post above "Upper bound implies worst case. I was going to say that big Theta is average case, .." etc. )
Again a good book on the fundamentals is the best way to resolve this (vs argument on HN). I suggest "Concrete Mathematics". Chapter 9 explains O, Theta, etc with functions with no algorithms in sight.
Once you learn the underlying math, applying that math to algorithmic analysis is trivial. Going the other way might lead to fundamental errors (though it need not, really) as demonstrated in your reply to btilly for e.g.
Now, with respect, I will exit this thread. I've given plenty of references to the proper definition and use of Oh, Theta etc notation in both algorithmic and non algorithmic contexts in my posts. (Strang, Knuth, Cormen etc).
If you want to follow up and read those, that's fine. If not, that is fine too. Arguing over mathematical notation without first reading the texts is (imho) a waste of everyone's time.
I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant:
>A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.
Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.