explain xkcd - User contributions [en]

2939: Complexity Analysis

2024-05-30T10:33:01Z

162.158.2.124: /* Explanation */ It is upper bound for time complexity, but average time complexity is still usefull.

{{comic
| number = 2939
| date = May 29, 2024
| title = Complexity Analysis
| image = complexity_analysis_2x.png
| imagesize = 430x361px
| noexpand = true
| titletext = PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough on proving P=NP.
}}

==Explanation==
{{incomplete|Created by a PERPETUALLY OPTIMISTIC BOT - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
[[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written as O(n log n), in {{w|Big O notation}}, expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger.

The "best case" for an algorithm is typically its runtime when its inputs have optimal values and it runs in as little time as possible. The joke here is that not only does it run quicker than this by being terminated early because it's 'unnecessary', but its runtime appears to be an hour shorter still because of an act of Congress changing {{w|daylight saving time}}, giving it an end time (in local time) that is an hour less than it would otherwise have been. Potentially this would result in an end time that is less than its start time, and therefore an apparently ''negative'' 'runtime'. Daylight saving time is a [[:Category:Daylight saving time|recurrent theme]] on xkcd, and it is clear that Randall is not a fan, so Congress making surprise DST changes is another way for Randall to mock the concept.

The "worst case" refers to the movie {{w|Groundhog Day (movie)|Groundhog Day}}, in which the same events occur over and over in a sort of time loop. (This movie has been referenced before in [[1076|1076: Groundhog Day]].) If the hardware running the algorithm is stuck in this kind of loop that resets to a previous time before it ever gets finished, then the algorithm would never terminate. This gives rise to a philosophical question as to whether the whole world is reset after every day, or just the town where the movie takes place. If it is just the town, and you can still connect to their hardware from outside, then from that perspective the algorithm would appear to be taking an interminably long time to run. If the whole world resets, since people (aside from the movie's main character) do not experience the reset of the day, it would only appear to take as long as it did on the final day when it successfully completed.

This may be an indirect reference to the {{w|halting problem}}, a famous problem in computer science. The halting problem is {{w|undecidable}}, meaning that there is no general algorithm that can tell whether a given algorithm will halt.

The title text refers to perhaps an even more famous problem in computer science: {{w|P versus NP problem|P versus NP}}. This asks whether every problem whose solution can be quickly verified (in nondeterministic polynomial time, {{w|NP_(complexity)|NP}}) can also be quickly solved (in polynomial time, {{w|polynomial time|P}}). The P-versus-NP problem is one of the seven {{w|Millennium Prize Problems}}, and as such has a $1 million prize for its solution. Presumably, the problem discussed here is in NP, so if P=NP, its worst-case runtime would be some polynomial ''O(n<sup>k</sup>)''. However, P vs. NP is a Millennium Prize Problem for a reason, and most computer scientists expect that P != NP, so hoping for a breakthrough in proving P=NP is "perpetually optimistic". This may be a reference to {{w|Optimism bias}} and the {{w|Planning fallacy}}, whereby people tend to assume that the most favourable outcome will be the most likely.

==Transcript==
:[Cueball is holding a presentation pointer stick, pointing to a table behind him that towers above him. The table has a heading above it and then two columns and three rows. the first column is slim and the second much broader.]
:Results of algorithm complexity analysis:
:{| class="wikitable"
|Average case
|O(n log n)
|-
|Best case
|Algorithm turns out to be unnecessary and is halted, then Congress enacts surprise daylight saving time and we gain an hour
|-
|Worst case
|Town in which hardware is located enters a Groundhog Day scenario, algorithm never terminates
|}

{{comic discussion}}

[[Category:Charts]]
[[Category:Comics featuring Cueball]]
[[Category:Programming]]
[[Category:Daylight saving time]]
[[Category:Fiction]]

Talk:2696: Precision vs Accuracy

2022-11-11T00:54:31Z

162.158.2.124:

87.532% of all statistics are just made up. [[Special:Contributions/172.70.178.220|172.70.178.220]] 11:10, 9 November 2022 (UTC)

Why is 'Barack Obama is 6'1"' and 'Barack Obama has 4 legs' medium precision? It seems to give exact value, so high precision. [[User:Tkopec|Tkopec]] ([[User talk:Tkopec|talk]]) 11:44, 9 November 2022 (UTC)
: OK, I get it. 6'1" means something between 6'0.50" and 6'1.49". For height it's OK, but when counting legs, it seems like a stretch. [[User:Tkopec|Tkopec]] ([[User talk:Tkopec|talk]]) 12:30, 9 November 2022 (UTC)
:: The four legs are probably considered to be only medium precise, not because of the number but because of the imprecise term "leg". While humans can walk on all four extremities, thereby using them as legs, the upper two are commonly referred to as arms. [[User:Bischoff|Bischoff]] ([[User talk:Bischoff|talk]]) 14:54, 9 November 2022 (UTC)
:: (ECed by Bischoff) Plus a person's height (excluding differences to footwear and perhaps hairstyle) varies by an inch or so over the course of a day, as the spine compresses whilst mostly upright (would depend a bit upon your daily activities, but "an inch" or 2-3cm is the typical quoted value, with all the questions about precision ''as well as'' accuracy). Within an inch of such a foot-and-inch value is basically between slightly over a percentage point of drift across a continuum of ultimately non-integer values.
:: The number of legs is ''generally'' a whole number (perhaps lower-limb amputees could claim "half a leg", but is that for above the knee or below or... that's beyond my wish to define, I would leave it up to the individual amputee to finesse to their own liking) and assigning decimals, even .000(recurring), would be ''over-''precise. A definite plain figure (however inaccurate) being the happy and acceptable medium between that and the vague imprecision (never mind inaccuracy) of the kind in the cell below. [[Special:Contributions/172.71.178.137|172.71.178.137]] 15:00, 9 November 2022 (UTC)
:::The medium is because it says most, and not all! --[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 08:08, 10 November 2022 (UTC)
::::It says "most cats", indeed, but the above was about Obama, singular. Though I think it's covered anyway... [[Special:Contributions/172.70.85.25|172.70.85.25]] 09:44, 10 November 2022 (UTC)

Someone should add an explanation of the difference between precision and accuracy. [[User:Nutster|Nutster]] ([[User talk:Nutster|talk]]) 13:13, 9 November 2022 (UTC)
:Tried it myself. Maybe made it too compact, but I often go on too long so I tried made it as brief and snappy as I felt I could. Over to other editors to rewrite or replace. [[Special:Contributions/172.71.178.137|172.71.178.137]] 15:00, 9 November 2022 (UTC)
::That there is confusion over this was a bit of a surprise to me, about 20 years ago, when I worked (as I did for many years) in the outdoor pursuits trade. GPS units would give a 12-character grid reference (1m<sup>2</sup>), but couldn't be relied upon to that level. I would tell people they're more precise than they are accurate, until it became apparent that they were waiting for me to complete the joke they thought I'd begun, as I was so clearly contradicting myself, what with the two words meaning identical things.
::Having gone on to explain the difference between the words, the neat brevity I'd sought was lost.
::Obviously they can be used sort of interchangeably in casual conversation, but I thought the difference was well enough known that, when talking about a navigational instrument, it would be obvious what was meant.
::Nope. [[User:Yorkshire Pudding|Yorkshire Pudding]] ([[User talk:Yorkshire Pudding|talk]]) 20:18, 9 November 2022 (UTC)
:::I deal with OS Grid References a lot, in a similar context, and a number of people who give 10-digits or more (2x5, for 1m res) from devices that typically don't ever settle down to less than 3m, and provably can be tens of metres off if there happens to be a small tree or shrub nearby.
:::(In fact, the other day I was geohashing myself, and my device was insisting I was in a totally different bit of the open field, 50m or so, no matter how much I sat it down at the provably correct point and wandered away so that even ''I'' wasn't obscuring its view of the sky. But it was good enough for me, which was all I do it for, so after giving it 5 minutes I counted it as done.)
:::And, in yet another activity, the publicised information for an event included a 12ish-DP reference for the starting area (vaguer than that), but just the ''postcode'' for the HQ (a very definite building that you could bullseye on a map), in a rural area where it covered half the valley! [[Special:Contributions/172.70.86.12|172.70.86.12]] 22:19, 9 November 2022 (UTC)

How is 17.082 palindromic? [[User:Barmar|Barmar]] ([[User talk:Barmar|talk]]) 14:54, 9 November 2022 (UTC)
:My error, I meant an anagram! (Was going for "anagramic", and my brain clearly rebelled.) [[Special:Contributions/172.71.178.137|172.71.178.137]] 15:00, 9 November 2022 (UTC)

High Precision High accuracy, Randal Munroe misses when Obama was president. Low precision Medium-rare accuracy, so do we, Randal, so do we. {{unsigned ip|172.70.130.154 }}

It is so annoying that the US uses . and , to mean the opposite of what most European countries (including Denmark where I live). So when I read this it states that Obama was president less than 3 days (70 hours) but it more than 70000 feet tall. :-) Of course I now the difference but I have to think about it more than if everyone used the same standard. Also height should use SI units as everyone should ;-) (weight given in number of cats is the new SI unit as far as I know, but don't use inches and feet ;-D ) --[[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 08:17, 10 November 2022 (UTC)
:Well, as a UKian, I was happy enough. Tell you what, though, let's develop a [[927: Standards|new and mutually-acceptable standard notation]]... ;) [[Special:Contributions/172.70.85.25|172.70.85.25]] 09:44, 10 November 2022 (UTC)
::Good idea. Lets meet on [[2562|11/12/22]] to discuss the details. --[[User:Lupo|Lupo]] ([[User talk:Lupo|talk]]) 13:41, 10 November 2022 (UTC)

I think Randal missed an opportunity to clarify how high precision can make something inaccurate. He could have said that Obama is 6’ 1.02173” tall, which would clearly be very precise, and also clearly inaccurate, simply because of the excessive precision. [[User:John|John]] ([[User talk:John|talk]]) 15:22, 10 November 2022 (UTC)
:Saying 6'1.0278 would have been more in theme, there. And it would be not really more inaccurate (might even be closer to the truth...) but would convey a false precision.
:Interstingly, when Andrew Waugh measured Mount Everest (before it was so named) he got a diffraction-adjusted figure of 29,000 feet, but decided to announced that it was 29,002 so that it didn't just like a rough figure rounded to the nearest hundred or even thousand feet. This made him the first person to put two feet on the top of Everest!
:(...The actual error was not bad, given his measurements had to be made from hundreds of miles away. Current official measurements with on-the-spot modern GPS say 29,031.7 feet (for the snow-peak, which is all that Waugh could mention), after 170ish years of (by some estimates, but contested) about a foot of extra height per decade through the continuing techtonic raising of the Himalaya. And any unknown differences in snow-depth. Certainly it was within tens of feet, i.e. a dozen or so metres. With a bit of an error-bar, but not really that big when you consider it...)
: So, arguably, that case was a deliberately false accuracy to help convey the true precision. [[Special:Contributions/172.70.90.3|172.70.90.3]] 16:15, 10 November 2022 (UTC)

I was expecting maybe a reference to Schrödinger's President when I first read the comic - but later realized that this could have been misconstrued as a threat. Oops!

2055: Bluetooth

2018-10-14T22:39:05Z

162.158.2.124: /* Explanation */

{{comic
| number = 2055
| date = October 5, 2018
| title = Bluetooth
| image = bluetooth.png
| titletext = Bluetooth is actually named for the tenth-century Viking king Harald "Bluetooth" Gormsson, but the protocol developed by Harald was a wireless charging standard unrelated to the modern Bluetooth except by name.
}}

==Explanation==
{{w|Bluetooth}} is a technology invented in the mid 1990s and intended for devices to connect wirelessly over a relatively short range for the purpose of transmitting information and/or audio. For example, a headset that connects via Bluetooth could be connected to a computer that's also Bluetooth-enabled, and then whatever would normally come out of the computer's speakers would come out the headset's ear pieces instead, and whatever was spoken into the headset's microphone would be transmitted to the computer's audio input system as if coming in through the computer's microphone. For this to work, the two devices need to be paired, which means they need to know the unique identification number of the other device and have been given permission to communicate with it, as well as knowing what kind of data exchanges are both possible and allowed. Pairing is not always a smooth process, especially given the somewhat limited methods some of these devices have for user interaction. For example, headsets typically don't have screens and user interfaces that make it easy to select what computer or other device you want them to connect to, so you're often confronted by blinking lights and/or sounds to make it through the pairing process, with each device having its own method for initiating or accepting a pairing request.

[[Cueball]] is talking to [[White Hat]] about {{w|Bluetooth}} and wireless connectivity. He asks if it has become easier to stream audio via Bluetooth since he last used it. White Hat then jests that it has become an easy-to-use and streamlined service, where connecting devices is easy, and he gives some examples of how easy it is to use. Cueball is excited about this, until White Hat reveals that he was lying and that Bluetooth is still as hard to use as ever. Cueball then invokes the name of "Josiah Bluetooth", a fictitious person implied to have invented the eponymous Bluetooth. "Josiah" is an old-timey name and suggests the amusing idea that in the 1700s or 1800s a hardy inventor named Josiah Bluetooth came up with the idea for wireless audio. (Note that while there is no "Josiah Bluetooth" person, there is a "[https://www.impossible.com/josiah/ Josiah]" Bluetooth ceramic speaker.)

This comic also references the common problem of audio playing through the wrong device when Bluetooth is activated.

The title text is another misdirection joke because while the first part of the sentence is true (Bluetooth was indeed named after a tenth-century Viking king), it goes on to make the silly claim that King Harald himself developed a wireless charging standard. This is a reference to the {{w|Qi_(standard)|Qi wireless power transfer standard}} that, like Bluetooth, is a well-branded industry standard with a catchy name and wide adoption that also does not work quite as well as promised even 10 years after its first release. (It could also be a reference to Medieval Vikings charging into battle, which is, by most accounts, usually a fairly wireless affair (assuming one discounts chainmail armor).)

Specifically, the Viking king referenced in the title text, {{w|Harald Bluetooth|Harald “Bluetooth” Gormsson}}, usually called Harald Bluetooth, was a ruler of Denmark and Norway who died in 985 or 986. Jim Kardach of Intel named the Bluetooth protocol after him, apparently as he united the various Norse tribes of Denmark into a single kingdom just as Bluetooth unites communication protocols. The {{w|Bluetooth#Logo|Bluetooth logo}} unites the two Norse {{w|runes}} corresponding to "H" and "B" for Harald Bluetooth.

==Transcript==
:[Cueball and White Hat are talking, Cueball is holding a cell phone and wireless headphones.]
:Cueball: I haven’t used a wireless/bluetooth thingy in like ten years. Is audio stuff still a nightmare?
:White Hat: Nah, it’s great now.

:[Zoom in on White Hat, Cueball is off-screen.]
:White Hat: You tap devices together twice to link them and they flash in sync. (It pairs using accelerometer timing and sound.) Tap them three times to disconnect.
:White Hat: You can pair multiple inputs and outputs and it handles it smoothly.
:Cueball (off screen): Nice!
:White Hat: It just works. Sound comes from where you expect.
:Cueball (off screen): Wonderful.

:[Zoom out to White Hat and Cueball facing each other.]
:White Hat: Haha, just kidding, it’s a nightmare.
:Cueball: ''Noooooo!''
:White Hat: When I connect to my car, music starts blasting from my headphones while the car repeatedly plays a “New connection!” chime.
:Cueball: ''This is not what Josiah Bluetooth intended!''

{{comic discussion}}

[[Category:Comics featuring Cueball]]
[[Category:Comics featuring White Hat]]
[[Category:Computers]]
[[Category:Smartphones]]

Talk:1970: Name Dominoes

2018-03-21T23:07:52Z

162.158.2.124:

This comic is a long list of names overlayed onto black domino tiles, arranged so that each touching side corresponds with the first or last name of another person. This will be difficult to transcribe. {{unsigned ip|108.162.221.53}}
:Would it be possible to use a fixed width format and try and transcribe like an actual scrabble board? I think there are unicode characters for upside-down and rotated text that we could use for the flipped names. But yes, definitely will be difficult.[[Special:Contributions/172.68.211.244|172.68.211.244]] 18:21, 21 March 2018 (UTC)
::The transcript doesn't need upside-down and rotated text. It should be enough to mention that some tiles are. A first draft with all names would be good, but even mentioning all the connections would be to complex to read. Think about the reader... --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 18:39, 21 March 2018 (UTC)
::How about using a fixed-width font and then representing each domino with an alphanumeric character, and then put a list below of what each character corresponds to? Even though there are more dominoes than characters, duplicate uses of a character (but referring to different names) can be easily disambiguated if we assign each character in order, left to right and top to bottom. [[Special:Contributions/172.69.70.71|172.69.70.71]] 20:04, 21 March 2018 (UTC)

I see alternative names or nicknames sometimes matches together. But is the Chris Pratt/Chris Evans match with Topher Grace a bit of a stretch? I see that Topher is a variation of Chris'''topher''' and Chis is a shortening of the same. But I guess it must be an acceptable move if Randle put it in the comic. Maybe it’s worth special points or something. [[Special:Contributions/162.158.38.70|162.158.38.70]] 18:14, 21 March 2018 (UTC)TheStewart

Walter White/Walt Whitman is a reference to Breaking Bad. [[Special:Contributions/172.68.58.101|172.68.58.101]] 18:20, 21 March 2018 (UTC)Pat

And Garnet being used to join Ruby and Saffire is clever...
[[Special:Contributions/141.101.98.64|141.101.98.64]] 18:23, 21 March 2018 (UTC)
This is a reference to Steven Universe where there is a character, Garnet, who is a fusion of Ruby and Sapphire.

"The title text spells out a rule that a player may only place a tile if they know who that person is" is mention as a reason for it not to be a fixed set of dominos, But I took it to mean you can't use "Jim Jones" unless you know of Jim Jones; as in, I could challenge your use of it by asking "okay who is he?". Maybe saying "oh, he went to school with me" or something wouldn't count, anymore than "crft is too a word!" works in Scrabble [[User:Afbach|Afbach]] ([[User talk:Afbach|talk]]) 19:36, 21 March 2018 (UTC)

Harrison Ford is from Blade Runner I believe. [[Special:Contributions/162.158.2.124|162.158.2.124]] 23:07, 21 March 2018 (UTC)