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.
Please sign and date your posts by typing four tildes ( ~~~~ ).
New to Wikipedia? Welcome! Ask questions, get answers.

Article policies

Archives: 1, 2, 3

This article is of interest to the following WikiProjects:

WikiProject Computing

(Rated 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.

B

This article has been rated as B-Class on the project's quality scale.

Mid

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

WikiProject Mathematics

(Rated B-class, Mid-importance)

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.

Mathematics rating:

B Class

Mid Importance

Field:

Analysis

One of the 500 most frequently viewed mathematics articles.

WikiProject Computer science

(Rated 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.

B

This article has been rated as B-Class on the project's quality 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 :
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}}

Big O notation has been listed as a level-5 vital article in Mathematics. If you can improve it, please do. This article has been rated as B-Class.

Removed polylogarithmic[edit]

Reinstated my VERY bad. Missed a bracket — Preceding unsigned comment added by 129.78.208.4 (talk) 22:17, 29 November 2006 (UTC)

"Tight" bounds?[edit]

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.— Preceding unsigned comment added by 128.97.82.220 (talk) 20:21, 10 September 2009 (UTC)

I don't feel a definition fits here, but I added a wikilink the first time the term is used. LudwikSzymonJaniuk (talk) 08:36, 9 April 2019 (UTC)

Inconsistency in definition of the big Omega notation[edit]

With the current definitions in the table in the section "Family of Bachmann–Landau notations", we have

f(n)=\Omega (g(n))\Leftrightarrow \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\geq k\cdot g(n)

So that

n=\Omega (-n^{2})

This is probably a mistake, which (I think) can be fixed by taking the absolute value of g(n) on the right side of the equation.

Having $n=\Omega (-n^{2})$ leads to an inconsistency: According to the section "The Knuth definition" we have

f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))

And so we should have

-n^{2}=O(n)

Which is obviously not consistent with the definition of the big O notation in the table in the section "Family of Bachmann–Landau notations":

f(n)=O(g(n))\Leftrightarrow \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq k\cdot g(n)

I understand that this is a minor problem since it is not very usual to take the big O or big Omega of negative functions, but I still think the definitions should be consistent in order to prevent confusion.

I'd like to hear your thoughts (or corrections, if I'm wrong in any of my observations). — Preceding unsigned comment added by 83.85.150.155 (talk) 20:22, 1 December 2018 (UTC)

The test function g is assumed to be positive. This is clearly stated at the beginning of the page. Sapphorain (talk) 21:39, 1 December 2018 (UTC)

anhducwiki

Wednesday, April 15, 2020