Talk:Big O notation
|This is the talk page for discussing improvements to the Big O notation article.|
|Archives: 1, 2|
|This article is of interest to the following WikiProjects:|
|This article has an assessment summary page.|
This is also referred to as "Order Notation"
eg. f(x)=O(x^2) would be stated as "f(x) has order x squared". It may be a North American way of calling this, but no-one in Australia or Britain ever calls this "Big O Notation". It sounds very childish. We simply refer to this as "Order Notation" which is what the original author called it.
- There appears to be some confusion here. "f(x) has order x squared" is usually abbreviated by . "f(x)=O(x^2)" has a very different meaning, which could (somewhat unprecisely) be worded as "f(x) is at most of order x squared" (with the understanding that f(x) could very well have an extremely irregular behaviour, with no clear order to speak of. Sapphorain (talk) 08:52, 12 June 2014 (UTC)
Proper way to 'say' Big-O notation
I am not a native English speaker. I was wondering if this article should mention the proper, or any, way to say Big-O in spoken English. For instance, I don't know which one better: "this algorithm has a Big-O of n squared," "this algorithm has a complexity of n squared," or "this algorithm is n squared."
Algorithms and their Big O performance
I'd like to put in some mention of computer algorithms and their Big O performance: selection sort being N^2, merge sort N log N, travelling salesman, and so on, and implications for computing (faster computers don't compensate for big-O differences, etc). Think this should be part of this write-up, or separate but linked?
- I think separate would be better, to increase the article count :-). Then you can have links from the Complexity, Computation and Computer Science pages. Maybe you can call it "Algorithm run times" or something like that. --AxelBoldt
- Or something like analysis of algorithms or Algorithmic Efficiency since you may sometimes choose based on other factors as well. --loh
- I'd recommend puting it under computational complexity which earlier I made into a redirect to complexity theory. It should be a page of it's own, but I didn't want to write it ;-) --BlckKnght
Reinstated my VERY bad. Missed a bracket
The article refers to terms "tight" and "tighter", but these terms are never defined! Alas, other pages (e.g. "bin packing") refer to this page as the one giving a formal definition of this term; moreover, "Asymptotically tight bound" redirects here. Yes, the term is intuitively clear, but a math-related page should have clear definitions.
I think a short section giving a formal definition of the term "tight bound" and referring to Theta-notation is needed (e.g. as a subsection of section "8. Related asymptotic notations"), and once such a section is created the redirection from "Asymptotically tight bound" should link directly there.