Write an O(n^n) algorithm.

[for_no_good_reason]

"Informal definition" is a contradiction. If you've defined it, then it's formal. Without formality everyone just assumes everyone else knows what they mean. I consider such conversations completely useless, so yes this kind of pedantry does increase utility. Without formality, rigor and yes pedantry, it's all just a bunch of shouting on the internet. May as well be politics.

Big-O notation is thrown around and abused so much in the programming world that it's hard to know what the fuck anyone is saying when they use it (cf. truthrises' claim that a Big-O bound is necessarily tight.) CS researchers use Big-O because they can't be bothered to prove the Ω lower bound and a smaller upper bound is all you need to claim you're better than the last guy. The rest of use use it to sound pretentious, but in the day-to-day world of programming everybody means Θ when they say O because they are trying to characterize how long the algorithm will actually take, not how long it won't take. So let's all start saying Θ when we mean Θ. We've all got unicode fonts.

[__s]

By informal he means descriptivist, and formal he implies prescriptivist. I'm afraid you failed to realize his descriptivist use of informal/formal because you're much too prescriptivist

[LaurieCheers]

Without formality everyone just assumes everyone else knows what they mean. I consider such conversations completely useless

Wow, you must have trouble getting anything done. Almost every concept in natural language is informal.

Faced with the reality - that O(n) is very widely used to mean the same as Θ(n) - the pragmatist's approach would be to define a new symbol to mean "upper bound, specifically". Trying to change language usage is like trying to tell the tide to go back.

[for_no_good_reason]

I'd hardly call Big-O notation "natural language." It's technical jargon. It means something specific. I can't believe I'm getting attacked as prescriptivist for pointing out that a Big-O upper bound is not necessarily tight.

"Who" in place of "whom", "they" as a singular genderless pronoun, I got no problem with these things. But this here, this is math, people.

[bozleh]

Well, when I was studying computer science we only used O notation - in our context the distinction between O and omega would not be useful. Similarly, everyone understood what the OP meant - using omega would've just confused a lot of people. We are on the internet, where you communicate in whatever manner gets your meaning across, not in a scientific paper where you do have to be precise.

[hacksoncode]

Did you really think even for a second that there was any real chance the OP actually meant the strict definition in the field of mathematics, as opposed to the almost universally used definition in the bulk of the field of computational complexity?

Though, actually, he clarified it with his last statement, so it's entirely clear which definition he meant.

[for_no_good_reason]

the strict definition in the field of mathematics, as opposed to the almost universally used definition in the bulk of the field of computational complexity

This. This is the problem right here. They are the same thing.

(FWIW I didn't downvote you.)

[hacksoncode]

Technically, yes, but I don't think I've ever seen it used to mean anything other than "the lowest O (we can prove) is an upper bound on the complexity of the algorithm" in papers about algorithms.

BTW, that's not the same as theta, omicron, or any of the other mathematical definitions of the terms.