Talk:Big O notation

Contradictory articles

The Omnicron article claims that the Big-O notation has fallen out of favor because the confusion over Omnicron/O/0/etc.). This confusion isn't apparent in this article. Does one of the articles need to be updated? 74.64.73.24 (talk) 23:42, 26 November 2021 (UTC)

You mean Omicron. The passage you mention in this article (which is not sourced) is plainly false and should be corrected or simply suppressed altogether. The Oh- and oh- notations were devised by Bachmann and Landau in 1894 and 1908 with the latin letters O and o, not with the greek letter Omicron. --Sapphorain (talk) 10:15, 27 November 2021 (UTC)

I’ve just tagged it as uncited and dubious, but I would not object to removing it there. (It’s not the only dubious uncited material in that article.) —JBL (talk) 14:46, 27 November 2021 (UTC)

I removed this nonsense, and also moved the tag upwards: it seems equally dubious that this letter is used at all for any technical notation.--Sapphorain (talk) 16:02, 27 November 2021 (UTC)

The last line of this article makes a sourced claim that Omicron is or has been used, by Knuth. Of course it is not the original nor main interpretation of this symbol. But it might be enough of a use to allow it to be mentioned in the omicron article. —David Eppstein (talk) 18:04, 27 November 2021 (UTC)

Ok, I added a subsection on Knuth's interpretation. --Sapphorain (talk) 20:30, 27 November 2021 (UTC)

BTW, note that Knuth calls it "Big Omicron" only in the title of his paper ("Big Omicron and big Omega and big Theta") and nowhere in the body — I think he was simply making a joke. (O-micron = small O, so "big O-micron" is simply "O".) That is, he was calling "O" "big Omicron" just for parallelism with "big Omega" and "big Theta". (Also, in TeX, or at least as far as the original Computer Modern fonts go, there's no difference between "big Omicron" and (big) "O", just as there's no difference between "big Alpha" and (big) "A". Now of course with Unicode there's a distinction, but…) Shreevatsa (talk) 23:06, 17 May 2022 (UTC)

Query

What's "sup" in the "Limit Definitions" of "Big Oh" and "Big Omega (HLw)" at #Family of Bachmann–Landau notations ?? $\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}<\infty$ and $\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0$ Yashpalgoyal1304 (talk) 13:40, 6 June 2022 (UTC)

The source says limsup , and searching for it fetches this: Limit inferior and limit superior which researching on this page itself, is also mentioned in the sections: #Formal definition and #See also. Yashpalgoyal1304 (talk) 13:55, 6 June 2022 (UTC)

You seem to be disturbed by the space between "lim" and "sup" that you get when typing "limsup" in LaTeX, like in $\limsup$. Well, you better get used to it... --Sapphorain (talk) 14:21, 6 June 2022 (UTC)

No, it was not that. I had never even consciously encountered these terms: superior/inferior limits. Looking at it's wikip article's illustration now, I understand that it's just a fancy term for upper limit and lower limit lol. But yeah, thanks for the tip too, t'll definitely help me in future when using it in LaTex. Yashpalgoyal1304 (talk) 17:01, 6 June 2022 (UTC)

Label axes on graph

The first graph, which is labelled, 'Example of Big O Notation:', has the horizontal axis labelled x, which I think is correct, and the vertical axis, y, which I think is wrong. A label of y would imply it means the value of the function for a given input of x. However, I think that it should be some measure of computing power required to make the calculation such as time for a given computer. I do not understand Big O Notation so I may be wrong. Gourdiehill (talk) 08:07, 12 August 2022 (UTC)

Differential

If f=O(n^k), is df=O(kn^{k-1}). Is this true in general? Darcourse (talk) 04:51, 15 October 2022 (UTC)

Functions with O-notation bounded by something are not required to be differentiable. They are certainly not required to have nice derivatives. It is easy to turn a piecewise-constant function bounded by a polynomial, like $f(x)=\lfloor x\rfloor$, into a function that is continuous but very steeply increasing at the steps, so steep that its derivative exceeds your favorite bound, instead of being discontinuous. —David Eppstein (talk) 06:31, 15 October 2022 (UTC)

@David Eppstein: It might make sense to add your explanation as a tiny subsection "Derivative" of Big_O_notation#Properties. A smooth version of your function is f(x)=sin(x²); it could be used as an example which is infinitely often continuously derivable, in O(1), yet f′ is in O(x)\O(1); see File:Sin x*x.pdf for a plot. I'd also suggest a brief comparison with $f\leq g\not \Rightarrow f'\leq g'$ even if both derivatives exist. - Since the unavoidable notation "f(x)=O(g(x))" is physicists' fashion and rather misleading, such a clarifying section may be needed to answer near-at-hand questions like that of Darcourse. - Jochen Burghardt (talk) 14:13, 15 October 2022 (UTC)

Dear ladies and gentlemen! Big O-notation describes a function only «in its infinities» which means that the behaviour of the function close to the origin is totally irrelevant – including differentiability. So I consider a mention in the article as misleading and disinforming. –Nomen4Omen (talk) 14:29, 15 October 2022 (UTC)

Also, it would need a published source. —David Eppstein (talk) 15:42, 15 October 2022 (UTC)