explain xkcd - User contributions [en]

3026: Linear Sort

2024-12-18T16:34:54Z

172.71.114.107: 1e6 seconds = more than 11 days

{{comic
| number = 3026
| date = December 18, 2024
| title = Linear Sort
| image = linear_sort_2x.png
| imagesize = 385x181px
| noexpand = true
| titletext = The best case is O(n), and the worst case is that someone checks why.
}}

==Explanation==
{{incomplete|Created in Θ(N) TIME by an iterative Insertion Sorter working on a multidimensional array - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
A common task in programming is to sort a list, a list being a collection of related elements of data that are stored in a linear fashion. There are dozens of algorithms that have been created through the years, from simple to complex, and each has its own merits with regards to how easy it is to understand / implement vs. how efficiently it operates on the data.

The efficiency of an algorithm is measured in terms of O(), commonly referred to as "Big-O", which classifies the amount of time needed to execute the algorithm with respect to the size of the data. Specifically, the Big-O assignment describes the change in execution time when the size of the data set changes (typically, when it doubles). There are various measures of efficiency, such as:
<ul><li>O(1) - Constant, which means the execution time is independent of the size of the data</li>
<li>O(n) - Linear, which means the execution time varies in direct proportion to the size of the data</li>
<li>O(n log n) - "n log n", usually assigned to the fastest sorting algorithms</li>
<li>O(n2) - Quadratic", meaning the execution time is proportional to the square of the size of the data.</li></ul>
It can be proven that the best general-purpose sorting methods are "n log n". Thus, a sorting algorithm in linear time does not actually exist.

In computer science, the complexity of a problem can be described using {{w|Big O Notation}}. Operations generally take longer when they act on more elements (notated as "n"). A linear algorithm would be very simple: each element would take a short amount of time on its own, so the time it takes would be a multiple of the size of the list. For instance, if it takes one second to look at a picture, it would take ten seconds to look at ten pictures. So "look at a list of pictures" is a linear operation and would be described as having complexity O(n).

Sorting is more complex. The time it takes to sort a list of items grows quickly as you add more items to the list. The complexity of sorting algorithms generally ranges from O(n^2) to O(n*log n). For example, one way to sort is to look at all the values to find the first item, then look at all the values to find the second item, and so on until you've positioned every item in the right place. If "looking at a number" takes one second, then you could sort a list of 2 numbers in 4 seconds: look at both numbers, then look at them a second time. Sorting 3 numbers would take 9 seconds: look at all 3 numbers 3 times to find the right position. Sorting a deck of cards this way would take 52*52 seconds = about 45 minutes. You can probably read a card more quickly than that, but the point is that the amount of time it takes to sort a list grows faster the more items you are looking at. This is not the most efficient way to sort, but it gets the job done.

The 'linear' sort here uses the less efficient {{w|merge sort}} rather than linear taking linearithmic, or O(n * log n) time. It does not matter, however, because it `sleep()`s for 1e6 (1 million) seconds, i.e. more than 11 days, per item in the list by sleeping for that length of time minus the time it actually took -- converting it by brute force to linear time that is so slow that it will not overcome the O(n * log n) term for large datasets. It's linear because it's guaranteed to take a million seconds for every element in the list (regardless of how long that actual sort really took); double the list size doubles the number of millions of seconds it takes. No matter how inefficient the actual sort method is, it is very unlikely it would take longer than a million seconds per element (unless some super inefficient algorithm is used, e.g. BogoSort). It should be noted that for sufficiently large lists, Mergesort will take longer than the 1e6 seconds, at which point the sorting algorithm will stop being linear anyway. However, this issue will only arise at impractically huge lists (though with the extreme lengths of this proposed sorting algorithm, one could argue any length of list is impractically huge).

The title text refers to the {{w|Best, worst and average case|best and worst case}} of the sort. The joke is that by making the "best case" linear so bad that it is worse than the worst case, the real best case is someone just trusting that a "linear sort" is best and not questioning why it's so slow. The worst case now is someone investigating how it's possible a sort could be taking a million seconds per element and discovering the deception in the code.

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:[The panel shows five lines of code:]
:function LinearSort(list):
::StartTime=Time()
::MergeSort(list)
::Sleep(1e6*length(list)-(Time()-StartTime))
::return

:[Caption below the panel:]
:How to sort a list in linear time

{{comic discussion}}

[[Category:Programming]]

Talk:2889: Greenhouse Effect

2024-02-03T10:00:42Z

172.71.114.107: Use Co2 free instead of renewable.

First description! FIRST 🤑 [[User:42.book.addict|42.book.addict]] ([[User talk:42.book.addict|talk]]) 18:45, 2 February 2024 (UTC)

Is there a category or a name for the set of comics which make the observation of "x thing happened closer to Y thing than today"? --[[User:Raviolio|Raviolio]] ([[User talk:Raviolio|talk]]) 18:57, 2 February 2024 (UTC)
:Maybe Category:Timelines could work? [[User:42.book.addict|42.book.addict]] ([[User talk:42.book.addict|talk]]) 19:00, 2 February 2024 (UTC)
:It is also similar in structure to many of the comics in [https://www.explainxkcd.com/wiki/index.php/Category:Comics_to_make_one_feel_old| Category:Comics to make one feel old] but has a quite different theme [[Special:Contributions/172.69.6.156|172.69.6.156]] 23:06, 2 February 2024 (UTC)

Do we have a source for the "their answers closely match modern estimates"? that would be a good thing to add [[User:Happier7713|Happier7713]] ([[User talk:Happier7713|talk]]) 19:35, 2 February 2024 (UTC)

A nit -- the Newcomen atmospheric engine was invented in 1712 and is usually thought of as the first steam engine (at least of the modern, western, world). {{unsigned ip|108.162.245.36 |20:25, 2 February 2024}}
:The Newcomen was certainly started it, and tends to be somewhat overshadowed (I actually walked past ''the'' oldest still-in-place Newcomen beam engine, earlier today... never seen it working (by hydrau;ics, these days), but it's there). But its practical efficiency was limited by its operation, and it took (Boulton and) Watt to make it into the potentially mobile powerhouse that drove much of the really developed stuff (beyond mine-drainage/etc).
:Of course, it was also more fuel efficient, so if we'd have somehow done exactly the same amount of IR via Newcomen-style machines then we'd probably have accelerated the burning of resources across the same period, so... [[Special:Contributions/162.158.74.49|162.158.74.49]] 00:10, 3 February 2024 (UTC)

I would say we did plenty of work. In 1896, noone had any idea what renewable energy is. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 23:48, 2 February 2024 (UTC)

:There have been windmills and watermills and fire from wood for thousands of years. The real problem is fossils, which release co2 from millions of years. In my opinion, it's about the attitude of "the right to consume" instead of "the right to use". --[[User:LaVe|LaVe]] ([[User talk:LaVe|talk]]) 06:35, 3 February 2024 (UTC)

“yet after 128 years there’s been close to no progress to changing our infrastructure to be renewable-energy based.” That might or might not be true, depending on how you define “close to no progress” but regardless of that, the comic does not make any such claim, and that part should be deleted frm the explanation of the comic. [[Special:Contributions/162.158.186.35|162.158.186.35]] 05:06, 3 February 2024 (UTC)

:Given what has appeared in other xkcd comics with a global-warming theme, I think the "close to no progress" reaction is permissible. Whether it is accurate is remarkably hard for me to pin down. A study I found in 2014 said that annual per-capita energy consumption in the USA rose from 100MM to 350MM BTUs between 1900 and 1973, and has since remained almost constant. 1973, of course, was the Arab oil embargo, which stimulated massive investment in energy efficiency that continue to the present day. Each of us now uses many more things for the same energy - but the population is increasing, therefore so is the bulk carbon-dioxide loading. A 2023 US Government attempt to forecast energy use in the USA between now and 2050, I found to be both unreadable and unhelpful in terms of assessing whether we are gaining on energy efficiencies and transition to renewables. There simply were too many variables in the inputs. And as 2020 demonstrated, our response to energy challenges will be forced by economics, not climate politics or comics IMO. [[Special:Contributions/172.71.150.168|172.71.150.168]] 07:22, 3 February 2024 (UTC)

I was unable to find an article by "Crawford 1997" in which either of the quotes cited in the title text appear in full. They might appear in other articles included in the [https://www.jstor.org/stable/i399217 special issue of the journal Ambio] devoted to the work that Arrhenius and colleagues did in the last decade of the 19th century. The two articles by Elisabeth Crawford in that journal, one sole-authored and one co-authored, provide considerable context for the discovery, including the various competing theories about global warming that were being debated among scientists at the time, and the remarkable observation by Arrhenius that such warming was not a bad thing. According to the Crawford sole-authored paper, Arrhenius wrote (translation from Swedish), "It [global warming] "will allow our descendants, even if they only be those of a distant future, to live under a warmer sky and in a less harsh environment than we were granted." [[Special:Contributions/172.71.151.130|172.71.151.130]] 07:04, 3 February 2024 (UTC)

Arguably, it was Abraham Darby's invention of the coke fired blast furnace in 1709, that vastly increased iron production, was the real start of the industrial revolution and use of coal as a fuel. (It was actually banned in some places as being a dirty fuel for cooking and heating) Of course that would mess up the nearer to / further from dates that this series of comics use. [[User:RIIW - Ponder it|RIIW - Ponder it]] ([[User talk:RIIW - Ponder it|talk]]) 09:51, 3 February 2024 (UTC)

I would not use the expression "renewable-energy based.", but i would use "Co2 free" or similar. The main problem with climate change is CO2, not lack of renewables. Plus renewables are not the only CO2 free energy source. E.g. the nuclear energy is too a CO2 free energy source. And the only renewable source able to cover the baseload is hydropower, that is not available in the right amount everywhere. For instance take a look on Germany CO2 emissions.