Talk:Big O notation/Archive 4

Archive 1

Archive 2

Archive 3

Archive 4

Query for not monotonically increasing infinite asymptotics

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

@Sapphorain: Would you please be so kind and give an example in the literature of a not monotonically increasing infinite asymptotics big O notation. ―Nomen4Omen (talk) 20:29, 24 November 2021 (UTC)

This is a very surprising question. Open any introductory course in number theory and you'll find many such examples (in Landau's Handbuch: §19 (p. 83 and 85), §27 (p.100), §28 (p.101 and 102), §31 (p. 117), §32 (p.121), etc). --Sapphorain (talk) 00:46, 25 November 2021 (UTC)

I guess that the confusion arises with the term "analyzing algorithm" which is somehow identified with the section title "Infinite asymptotics​". Somehow these two terms are confronted with "error term" and "Infinitesimal asymptotics​" in the subsequent section. Clearly, I would place your reference to Landau's Handbuch into the second section, because all the examples and all commenting text in the first section is associated with analysis of algorithms – and monotonically increasing infinite asymptotics.
I agree that the asymptotics in Landau's Handbuch are also toward infinity; nevertheless they resemble very much some kind of error terms.
As a resolution, I'd like to propose a switch in the titles of the sections, namely "Analysis of algorithms" for the first section and "Number theory" or "Number theoretic approximations" for the second. Moreover, I'd propose to place the latter first, because its contents is more general and algorithms can be seen as a subset of number theory.
Btw., with both applications of big O, the approximative comparison function is monotonic (not necessarily strictly), in the algorithmic case always non-decreasing with the problem size and in number theory both directions happen: increasing and decreasing. This statement would critisize the figure File:Big-O-notation.png, because it shows the approximation g(x) as oscillating. –Nomen4Omen (talk) 12:27, 25 November 2021 (UTC)

 Comment: While for certain recursive algorithms the resource usage must be monotonic increasing in the input size, this does not hold for all algorithms at all. As a simple example, the square root of 1000000 can be computed (by hand) far more easily than that of 73. As another example, a BASIC interpreter may take much more time to execute a short program with sophisticated loops than a much longer program containing no loops (or backwards jumps) at all, but many comments. - Jochen Burghardt (talk) 17:06, 25 November 2021 (UTC)

 Comment: Of course, for almost every algorithm and almost every problem of it there is a better or worse solution, especially when run on a better or worse machine or coded with a better or worse software.
But as far as I can see this does NOT at all affect the asymptotic assessment of a specific better or worse algorithm. E.g. doing the square root of 1000000 better or worse by hand does not belong to the problems under asymptotic consideration, especially when compared to a better or worse BASIC program. –Nomen4Omen (talk) 17:27, 25 November 2021 (UTC)

But monotonicity is a global property, not an asymptotic one (whatever that could mean). In the picture you mentioned, both f and g are not monotonic, no matter how the behave right of x₀. Likewise, the BASIC interpreter cannot have a monotonic function of time consumption vs. input size, since there is one counterexample to that. - Jochen Burghardt (talk) 17:39, 25 November 2021 (UTC)

As I understand the article every big O definition is associated with a certain limit, very frequently +∞ very far away. Thus a big-O-statement tells something about exactly 1 point, but this 1 point may be indefinitely far away. What I'm trying to say: the big-O-statement catches this single point better when the comparison function is monotonic than when the comparison function oscillates. At least: for every oscillating comparison function there can easily be found a non-oscillating one which has the same limit (and is very frequently better understood than the oscillation). –Nomen4Omen (talk) 18:08, 25 November 2021 (UTC)

Big O is well defined for oscillating functions, like $\max(1,-1^{n}\cdot n^{3})$ (a function that could easily arise in worst-case algorithm analysis for, say, searching for a perfect matching in a complete weighted graph, with an immediate failure return when the input size is odd). Limits are not. —David Eppstein (talk) 18:56, 25 November 2021 (UTC)

I do not know what you want to say:

1. "Limits are not" ... not well defined, or what? (When limits are not well defined, they are no limits.)
2. You do know a problem which is ${\mathcal {O}}(\max _{n\in \mathbb {N} }(1,-1^{n}\cdot n^{3}))$?
3. Or do you mean $\max\{1,-1^{n}\cdot n^{3}\}$? With the braces $\{\}$ of a set (mathematics).
   Do you want to say: the problem has size $n$ and it takes $\max\{1,-1^{n}\cdot n^{3}\}$ seconds. Then where is the big-O?

So sorry, I am unable to catch your point! –Nomen4Omen (talk) 19:32, 25 November 2021 (UTC)

Re "You do know a problem": Yes. I gave an explicit example of an algorithmic problem with this running time in my earlier message, which you appear not to have read. Also, yes, "limits are not well defined" for some problems for which big O is fine. As for brackets versus parens: max as a multi-argument function rather than as an operator on sets is perfectly well defined and perfectly standard. Insisting that there is something wrong with my comment because I didn't use brackets is the sort of mindless pedantry that gives pedants a bad name. —David Eppstein (talk) 20:56, 25 November 2021 (UTC)

Sorry, I must have missed your earlier message. I have read only the one dated 18:56, 25 November 2021 (UTC). If you mean another one, pls pinpoint to it. What I get from your response:

1. As it appears I interpret your 18:56-msg correctly: I take $\max(1,-1^{n}\cdot n^{3})$ as running time. Is this then already big-O?
2. There do not exist limits which are not well defined, because a limit which is one is always well defined. A formula (which is intended to define a limit) may be not well defined, but then it defines none – and is not a limit.
3. Are there big-O uses which do not specify a limit? Pls give an example! Especially when big-O is fine.
4. So sorry for your well defined $\max()$. I understand it and understand that you are a very sensible person. But still, if you mean this formula $\max(1,-1^{n}\cdot n^{3})$ as a function in $n$, then where is big-O?

–Nomen4Omen (talk) 21:32, 25 November 2021 (UTC)

The big O in $O(\max(1,-1^{n}\cdot n^{3}))$ was omitted because we were talking about doing multiple things with the same function: using it in big O and using it in a limit. I assumed that all participants in this discussion would be intelligent enough to figure this out on their own. —David Eppstein (talk) 22:46, 25 November 2021 (UTC)

I suspected it!

No

I was absolutely sure of it. But I wanted that you make it explicit, so you are not able to deny it later.

Now, what do you think of the statement:

$O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.$

(taken out of Big O notation#Other notation).
I propose that you take $g(n):=n^{3}$ in place of your awkward $h(n):=\max(1,-1^{n}\cdot n^{3})$.
Isn't then $O(g)=O(h)$ according to the mentioned statement of CLR?
And $g(n)$ not oscillating?
And monotonic?
And a lot easier to read and comprehend?
Pls answer honestly!

Best regards, –Nomen4Omen (talk) 16:59, 26 November 2021 (UTC)

It would be a lot simpler, and mathematically correct, to write that all polynomial time bounds are $O(2^{n})$ rather than having to figure out the individual polynomial for each one. Nevertheless we prove tighter bounds when we can. In exactly the same way, $O(\max(1,-1^{n}\cdot n^{3}))$ is a tighter bound than $O(n^{3})$, because it describes the running time on all instance sizes more accurately. We usually do not use oscillating time bounds like this one but mathematically there is no reason we shouldn't. It is less accurate to write that the time is $O(n^{3})$, just as it is less accurate to write that the time is $O(n^{4})$ or $O(2^{n})$, even though those bounds would still be mathematically correct. As for your identification with $O$ as defining a set of functions, and then your subsequent supposed equality of two different such sets $O(g)=O(f)$: this is not how I use O-notation (I prefer to think of "= O(...)" as a combined piece of notation that puts the quantifiers in the right place rather than using sets and membership) but if you do use it in this way then this equality is just untrue. $O(\max(1,-1^{n}\cdot n^{3}))\neq O(n^{3})$. In particular $n^{3}\notin O(\max(1,-1^{n}\cdot n^{3}))$ because there is no $c$ that works for large odd values of $n$. Incidentally, although this example involves a non-monotonic function, similar issues arise with monotonic ones as well; for instance, a function could alternate between two polynomial growth rates over different intervals of values. I chose this one not so much because the oscillation is more extreme, but because it is easy to motivate from the point of view of algorithm analysis. —David Eppstein (talk) 17:42, 26 November 2021 (UTC)

1. "... a lot simpler ...": It is really very rare that I had to read such garbage.
2. "... is a tighter bound ...": Nothing against a tighter bound. But $\max(1,-1^{n}\cdot n^{3})$ as your running time is the tightest bound you can give. To what end do you add a big-O ?
3. "It is less accurate to ...": Taken as running time it may be less accurate. But it is big-O notation. There $O(\max(1,-1^{n}\cdot n^{3}))$ equals $O(n^{3})$ (see section Big O notation#Equals sign).
4. "As for your identification with O as defining a set of functions ...": It is NOT my identification, it is a quote from CLR (see above). They are authorities in the subject, in strict contrast to you. And fortunately the other cited sources and the authors of the article agree.
5. "how I use O-notation": How you use O, is totally out of any relevance!
6. "equality is just untrue" Yes, equality is untrue, see Big O notation#Equals sign which you seem not to have read.
7. "... similar issues arise ...": No, do not arise. Because big-O always describes an asymptotic behaviour, and NOT the running time of every input.

–Nomen4Omen (talk) 18:52, 26 November 2021 (UTC)

We add the big O because the actual running time of an algorithm involves an arbitrary factor converting steps of the algorithm to wall-clock seconds, that will vary depending on which computer you run the algorithm on. By using big O notation we can ignore these factors and compare the scaling behavior of algorithms independently of their implementations and target platforms. This is basic basic material taught to freshman computer scientists. Why are you editing here if you don't already understand it? —David Eppstein (talk) 19:05, 26 November 2021 (UTC)

Thank you. This is item #2. What to the other 6 ? –Nomen4Omen (talk) 19:28, 26 November 2021 (UTC)

Every time I answer one of your questions, you come back with six stupider questions. It's a waste of my time and does not appear to be likely to lead to improvement of the article. Find someone else to pester, on a different topic. —David Eppstein (talk) 19:51, 26 November 2021 (UTC)

No! My questions have been earlier.

And instead of answering you are trying to demoralize me: "Why are you editing ..." in post-19:05 and now "stupider" and "someone else to pester". Is this the only way you are able to respond to my really objective questions?

–Nomen4Omen (talk) 20:05, 26 November 2021 (UTC)

You should certainly remember – and everybody who watches this talk page is able to verify – that you were breaking into this thread on 18:56, 25 November 2021, totally voluntarily and without having been asked for. What happened from then on is that you entered pseudo-mathematical statements which contained inaccuracies and defects, which lead to many, many questions how you want to be understood. And questions which were answered by you only partially and only after heavily insisting. (Btw. there are not only the 6 questions mentioned by me on 19:28, 26 November 2021. Also outstanding is e.g. your attitude to the mathematical limit.) Strangely enough, you now complain of being pestered, whereas pestering started on 18:56, 25 November 2021 by you. But I had to learn that this is your personal attitude and that there is no hope of change and no hope for getting reasonable answers. In the end, I am very glad that you finally give up. –Nomen4Omen (talk) 12:59, 27 November 2021 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

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)

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)