Wikipedia:Articles for deletion/Big o list

The following discussion is an archived debate of the proposed deletion of the article below. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.

The result was delete. Tone 13:07, 3 February 2022 (UTC)[reply]

Big o list

[Hide this box] New to Articles for deletion (AfD)? Read these primers!

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

No clear scope or any indication of what the list is about. No refs, and the apparent topic also seems like it is untenable as a Wikipedia article. AryKun (talk) 08:36, 27 January 2022 (UTC)[reply]

Note: This discussion has been included in the list of Software-related deletion discussions. AryKun (talk) 08:36, 27 January 2022 (UTC)[reply]
Note: This discussion has been included in the list of Lists-related deletion discussions. CAPTAIN RAJU^(T) 08:37, 27 January 2022 (UTC)[reply]
Delete — No scope what-so-ever to find what the list if about. Might even fall under WP:CSD#A1 – Kavyansh.Singh (talk) 08:55, 27 January 2022 (UTC)[reply]
Delete. Wikipedia is not a WP:NOTTEXTBOOK. Ajf773 (talk) 08:56, 27 January 2022 (UTC)[reply]
Weak delete but a comment: so people know what this list actually is: It relates to Big_O_notation, and is closely related to the table at Time_complexity#Table_of_common_time_complexities. That table is organised as a set of different complexities of time, i.e. if you double the number of samples, and the time taken to process them goes up by a factor of 2, then the algorithm is working in linear time and is classed as O(n), but that table (in big-O notation) has examples of algorithms that work in certain times. This table (here in the AfD) is the other way round: it's a table of algorithms, giving the times (and storage-spaces) in which they work. There might be some value in such a table, but I'm inclined towards delete at the moment, because (1) there are so many algorithms that the table is going to end up truly enormous; (2) the O-notation times of notable algorithms can be described at the algorithm's own article; and (3) because as the table acknowledges, many algorithms can work in various different O-notation times depending on how the data being processed, and on the exact implementation of the algorithm (QuickSort is a good example of this). This makes it difficult to define what data to put in the table. There is no point in tabulating the worst case scenario if the reader doesn't know what the worst case is, whether it's likely to happen, and whether a good implementation will easily avoid it. There is no information in the current table that needs merging to others. A weak delete because the concept is important, and if the table were better explained, with a more rational approach to choosing its algorithms, I can imagine it being Keepable. Elemimele (talk) 13:49, 27 January 2022 (UTC)[reply]

Okay, I've done a re-think on what the table actually is, and substantially re-written things. The table is related to data-structures (and the algorithms required to handle them). We already have a disambiguation page of data-structures at List_of_data_structures, but this is not in table form and doesn't give an over-view of how they behave. The table we are considering deleting is a Big_O_notation description of how a handful of data structures behave. The topic is important to computer-science. I'm still with weak delete because the table contains only a handful of data-structures, and a lot of what I wrote struck out above still applies. But I do think (1) the table could be made into something useful if anyone wants to; (2) it could potentially be merged somewhere (Data_structure?? not sure); (3) I personally think it's outrageous to delete something merely because we're not sure what it is! We should try to find out, and then delete it if it isn't encyclopaedia-material. Elemimele (talk) 16:17, 28 January 2022 (UTC)[reply]

If this page is kept, it should me moved to a better title, and it should be linked from the list of data structures. I haven't linked it, and don't intend to populate it, if it's going to be deleted. Elemimele (talk) 16:18, 28 January 2022 (UTC)[reply]

What I am more concerned about it that are there any secondary reliable sources asserting that "Big o list" (not Big O notation) is a topic for scholarly research? Without that, I'm afraid the topic would not be notable, and Wikipedia is not an indiscriminate collection of information. – Kavyansh.Singh (talk) 17:42, 28 January 2022 (UTC)[reply]

On that I have to disagree with you completely, Kavyansh.Singh. Big-O notation is enormously well-known, basic stuff. It has its own WP article that's totally riddled with excellent referencing. It's used in every textbook on algorithms. Not only does it have its own article, but it's extensively used in most of our articles on algorithms (including Quicksort which I keep mentioning). It is as basic to the study of algorithms as the concept of the Volt, the Amp and Ohm's law are to electrical engineering. Delete this article if you don't think it's encyclopaedic, but to delete it because you don't believe that Big O notation is relevant in scholarly research is utterly, utterly wrong. I'm honestly not trying to be rude, but a certain basic understanding of the subject matter is necessary for a meaningful discussion of the article's deletion. Elemimele (talk) 21:26, 28 January 2022 (UTC)[reply]

@Elemimele: I am afraid, there is some misunderstanding. I never questioned the notability of Big O notation, because it is notable. In my previous comment, I explicitly asked "are there any secondary reliable sources asserting that "Big o list" (not Big O notation) is a topic for scholarly research?" (emphasis mine in this case). Do other sources have or use that same list we have here? And apologies if I am in any way wrong, I am not an expert in it. – Kavyansh.Singh (talk) 21:33, 28 January 2022 (UTC)[reply]

Sorry, Kavyansh.Singh, perhaps I wasn't very clear either. My argument is that the use of big-O notation to describe algorithms, including the important class of algorithms that are used to locate records, delete them and insert them, is a fundamental tool in the research of algorithms. So I personally think that big-O notation is inextricably linked with a subject of scholarly research. Really it comes down to whether we need a list of algorithms describing their efficiency. If we want that list, then it will have to use big-O notation, just as a list of the longest rivers uses km or miles. The big question is whether a list of data-structures by efficiency-of-manipulation is encyclopaedia stuff. I've asked at the computer science wikiproject for more input (I hope in a neutral tone, as I honestly don't mind which way this goes). ~This is proving quite a useful discussion, thank you! Elemimele (talk)

I am still bit reluctant to keep it, as I feel that would be an indiscriminate collection of information until that set of notations has been discussed in other sources. I know notability decides whether article would be kept or deleted, but, if we talk about verifiability: would you be able to provide citations to verify entries in the table? Regardless, thanks for the follow-up; I learnt something new today! – Kavyansh.Singh (talk) 21:57, 28 January 2022 (UTC)[reply]

Delete not sure what this is to be honest. Oaktree b (talk) 20:29, 27 January 2022 (UTC)[reply]
Delete. I think this is a mistitled tabulation of bounds for some basic data structures. But regardless, collecting it in this way without any sources appears to be original research, and the scope of what data structures to include is highly unclear. —David Eppstein (talk) 22:35, 28 January 2022 (UTC)[reply]
David Eppstein, Kavyansh.Singh, you've both quite reasonably asked for sources. For information, it could be sourced. Of the four data-structures currently in the table, three have exactly the same information in the info-boxes of their own articles, where the information is referenced. I haven't tracked down "queue". But I am inclined to agree with you both that it's not clear what structures should be included, and whether the table is all that useful anyway. Elemimele (talk) 10:15, 29 January 2022 (UTC)[reply]
I am not asking for sources for the individual facts, but for the idea of tabulating them like this. Who has published lists of data structures and their time bounds, and what data structures do they collect in their published lists? Otherwise what you have is original research by synthesis. —David Eppstein (talk) 17:36, 29 January 2022 (UTC)[reply]
@David Eppstein: Yes, such a thing has been done. This is just a blog, so it's not a great reference: [1] but contains a table very similar to the one in this article, just with a lot more data-structures. Here is another: [2]. And here is a third: [3]. There are many other places where the read/search/delete efficiencies of different structures are described successively, which is something reasonable to summarise with a table, e.g. here [4]. That the subject is also found in serious independent secondary sources is also clear, from this Springer publication: [5] whose title is "Efficient Algorithms and Data Structures", and which launches straight into Big-O notation. This is not my professional field, so I can't guarantee to find tables in sources with the respectability of the Springer one, but the fact that I've found three such tables on the first page of a Google search suggests strongly that the concept is not original research or synthesis, but is something that other people are doing on a regular basis. My Google search was for "efficiencies of data structures". Elemimele (talk) 18:54, 29 January 2022 (UTC)[reply]
Actually I'm now wondering whether the table is in any case doomed, because it is so, so similar to the tables in those sources. It would be impossible for a complete table to be anything different to what ScientistBuilder found at www.bigocheatsheet.com, meaning that (1) it runs the risk of looking like a copyright violation, and (2) we could simply use the bigocheatsheet site (or similar) as an external link in any relevant articles on data-structures. Elemimele (talk) 22:52, 29 January 2022 (UTC)[reply]
Is there a way to add data sources that are not in bigocheatsheet to create a synthesis and not an outright copyright violation? ScientistBuilder (talk) 22:54, 29 January 2022 (UTC)[reply]
Delete. Something like a Category:Data Structures with Linear Time Access et sequentia could be appropriate, but not this. FalconK (talk) 00:52, 29 January 2022 (UTC)[reply]
Delete This could be a canonical example of something that falls under Speedy Deletion Criteria A1. There is insufficient context to identify what it is about, beyond something to do with Big(O) notations... -- Rockstone^{Send me a message!} 01:09, 29 January 2022 (UTC)[reply]
The goal of the Big O list was to provide a helpful reference for Computer Science students studying different data structures. There is a website https://www.bigocheatsheet.com/ that has a list of run times and my goal was to do something similar to that. — Preceding unsigned comment added by ScientistBuilder (talk • contribs) 17:59, 29 January 2022 (UTC)[reply]

I realize that some data structures do not have clearly defined big o notation and so a table may not be possible. I also realize that Wikipedia is not a textbook. ScientistBuilder (talk) 18:01, 29 January 2022 (UTC)[reply]
Keep. Very notable. HelpingWorld (talk) 02:50, 2 February 2022 (UTC)[reply]
Merge into Big O notation and/or Analysis of algorithms where it would make an interesting section on practical examples of using Big O notation to convey information.Gusfriend (talk) 05:32, 2 February 2022 (UTC)[reply]
- Neither of these is a good merge target. They are on more general topics, not on cheat sheets for freshman data structures quizzes. —David Eppstein (talk) 07:01, 2 February 2022 (UTC)[reply]

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.