Talk:Big O notation

This is the talk page for discussing improvements to the Big O notation article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: 1, 2, 3, 4: 90 days

This article is of interest to the following WikiProjects:

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.

Computing B‑class Mid‑importance

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-importance on the project's importance scale.

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.

Mathematics B‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.

Computer science B‑class Top‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

B

This article has been rated as B-class on Wikipedia's content assessment scale.

Top

This article has been rated as Top-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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

Removed polylogarithmic

Reinstated my VERY bad. Missed a bracket

"Tight" bounds?

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.

Mnemonics

(Below "Family of Bachmann-Landau notation" table)

This "mnemonics" business appears very unclear and clumsy to me. I strongly suspect it is the private production of a well-intentioned wikipedia contributor. Neither Bachmann, nor Landau, nor Knuth (at least in the references cited) mentioned anything close to what is claimed below the "Bachmann-Landau" notation table. Knuth uses the word "mnemonic" in his paper, but only to refer to the fact that the symbol O is commonly used and has become a reference. I note in passing that the "mnemonic" concerning the Omega symbol refers to the Knuth version of this symbol, and not to the Hardy-Littlewood version (which is the only one Landau knew): so who in the world is supposed to have devised these mnemonic "recipes"? I still think a precise reference is very much needed to justify the conservation of this part in the article. Sapphorain (talk) 21:21, 3 September 2013 (UTC)[reply]

It looks much like OR to me. It would definitely need a proper source attribution, but anyway, I’m unconvinced this bit of trivia needs to be included in the (already quite long) article at all.—Emil J. 12:17, 4 September 2013 (UTC)[reply]

I suppressed the bit of trivia. The bibliographic references inside were suppressed too, but can be found elsewhere in the page. Sapphorain (talk) 22:08, 16 November 2013 (UTC)[reply]

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? 90.190.113.12 (talk) 12:34, 9 January 2014 (UTC)[reply]

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.