5 ms·

>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 theo

by endtime 16y ago

>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.

plinkplonk 16y ago
">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. This thread is getting too long. Over and out.

by endtime 16y ago

plinkplonk 16y ago

">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. This thread is getting too long. Over and out.