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.|
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.
f(x) versus f
Currently in this article, the notation f(x) is used to denote a function. In the articles Function (mathematics), Limit (mathematics) etc., f is used to denote a function (a rule for mapping numbers to numbers) and f(x) is unambiguously used to denote its value (a number). These are two different approaches to the notation of functions: in the first approach (used in this article), the letter f denotes a dependent variable or (physical) quantity, and when talking about the function's behavior, one must always say what variables are regarded as the independent variables or experiment parameters that it depends on; in the second approach (in Function (mathematics) etc.), f is the name of a function, where function is defined as a rule mapping objects to other objects. Perhaps the notation of functions should be unified in Wikipedia? 18.104.22.168 (talk) 12:34, 9 January 2014 (UTC)
Base of log?
Sorry if I missed it, but I couldn't find specified anywhere what base of log is being used. Does it not matter since it is only comparing orders? Or is it assumed to be base 2 since it's computer science? Thanks for any clarification. — Preceding unsigned comment added by 22.214.171.124 (talk) 20:06, 23 January 2014 (UTC)
- The base of the log does not matter once it is moved inside of Big-O. Changing the log base involves multiplying by a constant. Glrx (talk) 22:21, 25 January 2014 (UTC)
Hardy and Littlewood's Notation Section Is Problematic.
Not only is the paper incorrectly cited, but if you read the paper (available here: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1091181/pdf/pnas01947-0022.pdf), the letter Omega does not appear.
Discussion of the definition of limit superior as x approaches infinity is also absent from the paper, which is a relief because appears non-sensical to me. How can x approach infinity from above?
I'm inclined to strike this section from the page.
- You are looking at the wrong paper. The right one is here (probably behind a paywall, sorry). Also, there is nothing in that formula which says that x is approaching infinity from above. Incidentally, they do not use limsup in their definition and returning to the original version might help people with poor analysis background (like most computer scientists). Here is what they say:
- We define the equation f = Ω(φ), where φ is a positive function of a variable, which may be integral or continuous but which tends to a limit, as meaning that there exists a constant H and a sequence of values of the variable, themselves tending to the limit in question, such that |f| > Hφ for each of these values. In other words, f = Ω(φ) is the negation of f = o(φ).
- I think that the condition H > 0 is required and was omitted accidentally. McKay (talk) 04:13, 18 February 2014 (UTC)
- Incidentally, this is the definition most used in computer science even though that is rarely admitted. Consider an algorithm that takes time n2 for even n and is trivial (constant time) for odd n. This happens all the time but everyone writes Ω(n2) even though it does not satisfy the textbook definition of Ω that they claim to be using. McKay (talk) 04:13, 18 February 2014 (UTC)