Talk:Big O notation

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)

No, they are not just fancy terms for upper and lower limit. Maybe you should check the definitions again.2405:6E00:1ED2:1700:9DBE:839C:30C6:CE68 (talk) 09:36, 18 May 2023 (UTC)

Use in computer science

It seems, from the opening of this section, that it is meant to discuss the fact that some computer scientists use O where $\Theta$ should be used instead (i.e., for a tight bound); I'm not sure if it is desirable to discuss improper usages in the article. At any rate, the rest of the section does not match its beginning, as it illustrates the proper use. It should be edited, perhaps removed. AmirOnWiki (talk) 14:07, 30 June 2023 (UTC)

Determining if a binary number is even or odd changed to finding median

"Determining if a binary number is even or odd" isn't a particularly useful example, because there will only one number being tested. Finding the median value for a sorted list of measurements is a better example. SlowJog (talk) 02:32, 29 October 2023 (UTC)

Big O and data structures

My note on this topic disapeared, but I still think there is common misinterpretation there. Suppose you have algorithm which \Theta(n) times calls a method of a data structure. The assymptotic complexity of the method is described as O(\log s) where s is the size of the data structure. The actual use of the data structure is such that s never exceeds 1. (Weird case) If you simply multiply the number of method calls by their complexity you obtain bound 0.

There are several solutions of this wrong calculation ... I recommend considering the minimal complexity of a call be 1 what changes the result to \Theta(n). I do not think we would change all complexity descriptions to O(1+\log s) ..., but one should know about this use asymptotic when the size does not go to infinity problem.Hippo.69 (talk) 13:50, 12 December 2023 (UTC)

Are you talking about this discussion from three years ago? --JBL (talk) 17:11, 12 December 2023 (UTC)

Oh yes, and seems nobody else considers using assymptotic complexity for tiny data structures be a problem. Let us hope people are smart enough not to think n calls to a data structure could take constant/zero time in total and there is no need to emphasize that.

Hippo.69 (talk) 21:04, 14 December 2023 (UTC)

It makes no sense for the size of a data structure to be a positive number less than one. These sizes are generally integers: integer numbers of memory cells (bits, bytes, words, whatever) or number of elements stored. Occasional care needs to be taken with logs when the size can equal one, and people are often sloppy about that, but it's harmless.

In the meantime, the much bigger problem with O-notation is the use of it with more than one variable, without any specification of how the two variables are assumed to go to infinity together or separately. It's safe for the most common usage, for graph algorithms on connected graphs as a function of vertex and edge counts, because those two things are tied to each other in both directions, but even for disconnected multigraphs one runs into this issue. —David Eppstein (talk) 21:51, 14 December 2023 (UTC)

Yes, I was refering to the sloppiness with size 1 and log(s) (s not meaning the number of bytes or cells, but the number of represented items) (and I do not see a problem with data structure state representing 0 elements).

I actually am not sure where is the problem with the complexity bounded by more parameters going to infinity.

I interpret f(n_1,n_2,...,n_k)\in O(g(n_1,n_2,...,n_k)) as ... there exists c and n_0 that for all i 1<=i<=k and n_i>n_0 f(n_1,n_2,....,n_k)<c g(n_1,n_2,...,n_k). What problems it causes? Hippo.69 (talk) 08:00, 15 December 2023 (UTC)

So you are assuming that all n_i go to infinity at the same rate? But what if they don't? If an algorithm takes time O(f(x)+g(y)) according to your definition, and you hold x fixed while letting y grow, how much time does it take? —David Eppstein (talk) 08:13, 15 December 2023 (UTC)

No, I am assuming all n_i going to infinity where the rate does not matter. Of course there could be other constraints (typically m<n^2 ... edges and vertices) or (h<=n Kirkpatrick–Seidel h subset of n points), but it seems to me they are not relevant. Oh I have not read the x, y example ... if x is hold fixed, it does not go to infinity, but if goes to infinity, it seems to me it is fine using O as I have written. ... End of course there could be constants in the expressions f,g, but there is no variable and n_i connected to them ... may be try to show the confusing use in an exampleHippo.69 (talk) 08:38, 15 December 2023 (UTC)

But if you assume that all n_i are greater than some n_0, then you are assuming the rate does matter. Consider the function f(x,y) that is 2^y for x=1 but x^2+y^2 for x,y>1. For all x,y>n_0 (for instance n_0=2), it is less than some constant times x^2+y^2. Does that mean you can write that it is O(x^2+y^2)? It is, according to your definition. What if you plug in that time bound to an algorithm that, say, loops over all pairs (x,y) up to n? Can you just add the O(x^2+y^2) bound and get a valid answer? —David Eppstein (talk) 18:28, 15 December 2023 (UTC)

OK, I get your point. When the function is not monotone, the relative grow rate matters. Hippo.69 (talk) 21:02, 15 December 2023 (UTC)