News for hackers. Stuff that matters.
Re:A beginner's guide to Big O notation (2009) by umanwizard on Thursday May 05, 2016 @12:23PM (#11637461)
You'll be a lot happier if you mentally replace O(n) with Theta(n) every time you see it, rather than feeling the need to nitpick when you know that that's what people mean when they say O(n), 99% of the time.
Re:A beginner's guide to Big O notation (2009) by marcosdumay on Thursday May 05, 2016 @01:04PM (#11637874)
Problem is that Theta(n) is an almost useless notation.

Thus, most times people say O(n) on practice[1], they mean O(n). But most times people define O(n), they cite the Theta(n) definition.

It isn't hard to put an "up to", "no more than" or "or less" at the definition, and it does not make it threatening or hard to read.

[1] There's probably a small corner in Hell reserved for people that mean O(n) on average but refuse both to say that qualifier and care about what data distribution created that average.

Re:A beginner's guide to Big O notation (2009) by Lxr on Friday May 06, 2016 @11:45AM (#11644719)
There seems to be a misconception here that this has something to do with best/average/worst case input. "f(x) is O(g(x))" is a purely mathematical statement about two functions, and means that f(x) is smaller than or equal to (K times) g(x) for all x beyond some threshold. I.e. O(g(x)) is a set of functions that includes f(x).

When we say "quicksort is O(g(n))" for some g we also need to specify, or assume, the distribution of the input (i.e. best/average/worst case), and we are free to assume whatever distribution we like. Then, assuming that distribution, the running time of the algorithm is just a function of the input size, and we can use the above definition to make a statement about that function (i.e. what complexity class it is in).

A complete statement looks like "quicksort is O(n^2) in the worst case", which means "for every n, pick the list of length n that takes the longest to sort (i.e. the worst-case input), and the number of steps executed by quicksort will be no more than Kn^2 as long as n is large enough, for some fixed K".

The difference between O, Theta and Omega only concerns what functions the set contains - in particular, Theta(g(x)) is a subset of O(g(x)). This is a separate issue to whether we are talking about best/average/worst case input.

Re:A beginner's guide to Big O notation (2009) by jholman on Friday May 06, 2016 @07:26AM (#11643131)
I disagree.

In my experience, outside of technicality-penis-measuring contests (like this thread, or a few particular minutes during the class I was leading a few hours ago), every time someone says O(foo), they're describing an algorithm that they believe to be Theta(foo). On the other hand, I've never seen someone _define_ big-Oh and accidentally define big-Theta, which is unsurprising, given that the big-Theta definition is literally twice as much work to write out as the big-Oh.

Relatedly, Theta is a highly useful concept, except for that fact that it's much easier to type O(n) and also mildly faster to whiteboard it (relative to Theta(n)). Why do you think it's almost useless? Mind you, I don't think it's useful enough to care about the fact that most non-specialists can't keep track of the difference between these complexity classes.

Also, I question your claims about Hell, and what I take to be your implication that you disapprove of both saying using big-Oh to refer to average-case without saying so, and of saying "average" without specifying a distribution or an aggregation function.

To the former, that's how people use the language, and meaning average-case is 100% as reasonable as assuming that big-Oh always means worst-case. Big-Oh is a system for dividing arbitrary functions into nested equality classes (well, I guess maybe the right name for this is inequality classes?), and <<average-case resource consumption vs input size>> is just as useful an input function as <<worst-case resource consumption vs input size>>. There's no technical reason, and no pragmatic reason, to insist otherwise.

As for distribution, if someone doesn't specify distribution, it means they're implying that it's true across all the reasonable distributions that they can think would apply, just like it always means something like that when a human leaves out a detail. Every single time I've looked into a case like this, the assumed distribution is a uniform random distribution of all possible inputs. There are always things left unsaid, why claim that this particular elision is a sin?

Re:A beginner's guide to Big O notation (2009) by umanwizard on Thursday May 05, 2016 @11:48PM (#11641556)
What do you mean? Why's Theta(n) useless?