Talk:3026: Linear Sort - Revision history

95.71.113.152 at 22:23, 15 June 2025

2025-06-15T22:23:39Z

172.70.162.170 at 12:40, 25 December 2024

2024-12-25T12:40:42Z

172.71.98.138 at 08:23, 25 December 2024

2024-12-25T08:23:35Z

172.70.91.30 at 13:10, 24 December 2024

2024-12-24T13:10:01Z

162.158.154.104 at 10:14, 24 December 2024

2024-12-24T10:14:53Z

162.158.134.148: two replies

2024-12-23T21:36:23Z

two replies

172.68.205.178 at 21:22, 23 December 2024

2024-12-23T21:22:42Z

172.70.211.83: "y'all can't write" lol

2024-12-23T21:07:57Z

"y'all can't write" lol

172.70.58.45 at 20:01, 23 December 2024

2024-12-23T20:01:46Z

172.69.136.141: reply

2024-12-23T18:43:31Z

← Older revision		Revision as of 22:23, 15 June 2025
Line 134:		Line 134:
	Now, what efficiency '''this''' variant has in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation]?{{unsigned ip\|172.71.98.138\|08:23, 25 December 2024}}		Now, what efficiency '''this''' variant has in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation]?{{unsigned ip\|172.71.98.138\|08:23, 25 December 2024}}
	:Might depend upon the implementation of MergeSort(), as intrinsic parallelisation is possible (but becomes less relevent as you pass into n>2*threads), though it tends to be O(n log n) for worst and average cases, which the call to the unadulterated function that calls it won't do much to change. [[Special:Contributions/172.70.162.170\|172.70.162.170]] 12:40, 25 December 2024 (UTC)		:Might depend upon the implementation of MergeSort(), as intrinsic parallelisation is possible (but becomes less relevent as you pass into n>2*threads), though it tends to be O(n log n) for worst and average cases, which the call to the unadulterated function that calls it won't do much to change. [[Special:Contributions/172.70.162.170\|172.70.162.170]] 12:40, 25 December 2024 (UTC)
		+	::As such, maybe it should be something like "Print(MergeSort(List))" or "Return(MergeSort(List))"? --[[Special:Contributions/95.71.113.152\|95.71.113.152]] 22:23, 15 June 2025 (UTC)

← Older revision		Revision as of 12:40, 25 December 2024
Line 132:		Line 132:
	Return		Return

−	Now, what efficiency '''this''' variant has in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation]?	+	Now, what efficiency '''this''' variant has in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation]?{{unsigned ip\|172.71.98.138\|08:23, 25 December 2024}}
		+	:Might depend upon the implementation of MergeSort(), as intrinsic parallelisation is possible (but becomes less relevent as you pass into n>2*threads), though it tends to be O(n log n) for worst and average cases, which the call to the unadulterated function that calls it won't do much to change. [[Special:Contributions/172.70.162.170\|172.70.162.170]] 12:40, 25 December 2024 (UTC)

← Older revision		Revision as of 08:23, 25 December 2024
Line 125:		Line 125:
	:It's clearly targeted at those who take a statement that it's O(n) at face value. e.g. sorting(!) any {{w\|Sorting algorithm#Comparison of algorithms\|comparison list}} by the 'best sorting performance'. You'd have it pop up at the top just like a search engine's Sponsored Link, and there'll be people who'll 'click on it' through sheer lack of analysis. And it'd not be an outright lie, so an uncritical analysis wouldn't mark it as actually ''wrong''/delete it (it could sneak by an AI's basic 'understanding', perhaps, if not a human with any concept of algorithmic trolling) when it's probably far easier to establish its dubiously established ''bona fides'' than most sorting algorithm claims to O()ness.		:It's clearly targeted at those who take a statement that it's O(n) at face value. e.g. sorting(!) any {{w\|Sorting algorithm#Comparison of algorithms\|comparison list}} by the 'best sorting performance'. You'd have it pop up at the top just like a search engine's Sponsored Link, and there'll be people who'll 'click on it' through sheer lack of analysis. And it'd not be an outright lie, so an uncritical analysis wouldn't mark it as actually ''wrong''/delete it (it could sneak by an AI's basic 'understanding', perhaps, if not a human with any concept of algorithmic trolling) when it's probably far easier to establish its dubiously established ''bona fides'' than most sorting algorithm claims to O()ness.
	:But, really, it's just a Wicker Man suggestion. (Like a Straw Man one, where you destroy it specifically by burning.) [[Special:Contributions/172.70.91.30\|172.70.91.30]] 13:10, 24 December 2024 (UTC)		:But, really, it's just a Wicker Man suggestion. (Like a Straw Man one, where you destroy it specifically by burning.) [[Special:Contributions/172.70.91.30\|172.70.91.30]] 13:10, 24 December 2024 (UTC)
		+
		+	What about true linear sort? Will it work?
		+
		+	Function TrueLinearSort(list):
		+	MergeSort(list)
		+	Return
		+
		+	Now, what efficiency '''this''' variant has in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation]?

← Older revision		Revision as of 13:10, 24 December 2024
Line 122:		Line 122:
	::Please don't. [[Special:Contributions/162.158.134.148\|162.158.134.148]] 21:36, 23 December 2024 (UTC)		::Please don't. [[Special:Contributions/162.158.134.148\|162.158.134.148]] 21:36, 23 December 2024 (UTC)

−	Here’s what I don’t get about this joke: why would the recipient of this program ever initially think it was O(n)? Are there people who check the complexity of an algorithm by literally running it on a bunch of different inputs then fitting the time taken to a curve? That should be illegal!	+	Here’s what I don’t get about this joke: why would the recipient of this program ever initially think it was O(n)? Are there people who check the complexity of an algorithm by literally running it on a bunch of different inputs then fitting the time taken to a curve? That should be illegal! {{unsigned ip\|162.158.154.104\|10:14, 24 December 2024}}
		+	:It's clearly targeted at those who take a statement that it's O(n) at face value. e.g. sorting(!) any {{w\|Sorting algorithm#Comparison of algorithms\|comparison list}} by the 'best sorting performance'. You'd have it pop up at the top just like a search engine's Sponsored Link, and there'll be people who'll 'click on it' through sheer lack of analysis. And it'd not be an outright lie, so an uncritical analysis wouldn't mark it as actually ''wrong''/delete it (it could sneak by an AI's basic 'understanding', perhaps, if not a human with any concept of algorithmic trolling) when it's probably far easier to establish its dubiously established ''bona fides'' than most sorting algorithm claims to O()ness.
		+	:But, really, it's just a Wicker Man suggestion. (Like a Straw Man one, where you destroy it specifically by burning.) [[Special:Contributions/172.70.91.30\|172.70.91.30]] 13:10, 24 December 2024 (UTC)

← Older revision		Revision as of 10:14, 24 December 2024
Line 121:		Line 121:
	:Could do with more info... BRB... /goes to put +2345 bytes extra in with 'useful' additional information. [[Special:Contributions/172.68.205.178\|172.68.205.178]] 21:22, 23 December 2024 (UTC)		:Could do with more info... BRB... /goes to put +2345 bytes extra in with 'useful' additional information. [[Special:Contributions/172.68.205.178\|172.68.205.178]] 21:22, 23 December 2024 (UTC)
	::Please don't. [[Special:Contributions/162.158.134.148\|162.158.134.148]] 21:36, 23 December 2024 (UTC)		::Please don't. [[Special:Contributions/162.158.134.148\|162.158.134.148]] 21:36, 23 December 2024 (UTC)
		+
		+	Here’s what I don’t get about this joke: why would the recipient of this program ever initially think it was O(n)? Are there people who check the complexity of an algorithm by literally running it on a bunch of different inputs then fitting the time taken to a curve? That should be illegal!

@@ Line 116: / Line 116: @@
 :Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141|172.69.136.141]] 18:43, 23 December 2024 (UTC)
 ::Interesting, and it probably can do without saying the bit that is removed, but not for the reason given in the removal. As pointed out, above, practical timing issues don't depend upon the base computer being binary or not ("assume log-base-2 because computers are all binary" isn't really a useful argument). Some theoretical function creating and using a basic binary tree might (according to its operational needs) scale its operational speed by log-base-2 as a key factor, but a version that uses a k-d tree by log-base-k (you can imagine them being ultiately functionally equivalent by way of a Cantor-pairing(/tripling/etc) equivalence, if you want justification for this hypothetical choice between). They'd both be considered O(... log N ...), give or take any other accompanyting factors (or overriding terms). But you can't say that an O(... log N ...) solution will take a-specific-base-of-N multiple of time, certainy not base-2. [[Special:Contributions/172.70.58.45|172.70.58.45]] 20:01, 23 December 2024 (UTC)
 Thank you to whomever put us out of our misery. [[Special:Contributions/172.70.211.83|172.70.211.83]] 21:07, 23 December 2024 (UTC)
 :Could do with more info... BRB... /goes to put +2345 bytes extra in with 'useful' additional information. [[Special:Contributions/172.68.205.178|172.68.205.178]] 21:22, 23 December 2024 (UTC)

← Older revision		Revision as of 21:22, 23 December 2024
Line 118:		Line 118:

	Thank you to whomever put us out of our misery. [[Special:Contributions/172.70.211.83\|172.70.211.83]] 21:07, 23 December 2024 (UTC)		Thank you to whomever put us out of our misery. [[Special:Contributions/172.70.211.83\|172.70.211.83]] 21:07, 23 December 2024 (UTC)
		+	:Could do with more info... BRB... /goes to put +2345 bytes extra in with 'useful' additional information. [[Special:Contributions/172.68.205.178\|172.68.205.178]] 21:22, 23 December 2024 (UTC)

← Older revision		Revision as of 21:07, 23 December 2024
Line 116:		Line 116:
	:Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141\|172.69.136.141]] 18:43, 23 December 2024 (UTC)		:Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141\|172.69.136.141]] 18:43, 23 December 2024 (UTC)
	::Interesting, and it probably can do without saying the bit that is removed, but not for the reason given in the removal. As pointed out, above, practical timing issues don't depend upon the base computer being binary or not ("assume log-base-2 because computers are all binary" isn't really a useful argument). Some theoretical function creating and using a basic binary tree might (according to its operational needs) scale its operational speed by log-base-2 as a key factor, but a version that uses a k-d tree by log-base-k (you can imagine them being ultiately functionally equivalent by way of a Cantor-pairing(/tripling/etc) equivalence, if you want justification for this hypothetical choice between). They'd both be considered O(... log N ...), give or take any other accompanyting factors (or overriding terms). But you can't say that an O(... log N ...) solution will take a-specific-base-of-N multiple of time, certainy not base-2. [[Special:Contributions/172.70.58.45\|172.70.58.45]] 20:01, 23 December 2024 (UTC)		::Interesting, and it probably can do without saying the bit that is removed, but not for the reason given in the removal. As pointed out, above, practical timing issues don't depend upon the base computer being binary or not ("assume log-base-2 because computers are all binary" isn't really a useful argument). Some theoretical function creating and using a basic binary tree might (according to its operational needs) scale its operational speed by log-base-2 as a key factor, but a version that uses a k-d tree by log-base-k (you can imagine them being ultiately functionally equivalent by way of a Cantor-pairing(/tripling/etc) equivalence, if you want justification for this hypothetical choice between). They'd both be considered O(... log N ...), give or take any other accompanyting factors (or overriding terms). But you can't say that an O(... log N ...) solution will take a-specific-base-of-N multiple of time, certainy not base-2. [[Special:Contributions/172.70.58.45\|172.70.58.45]] 20:01, 23 December 2024 (UTC)
		+
		+	Thank you to whomever put us out of our misery. [[Special:Contributions/172.70.211.83\|172.70.211.83]] 21:07, 23 December 2024 (UTC)

← Older revision		Revision as of 20:01, 23 December 2024
Line 115:		Line 115:
	:What does this possibly have to do with explaining the comic? [[Special:Contributions/172.68.23.81\|172.68.23.81]] 18:07, 23 December 2024 (UTC)		:What does this possibly have to do with explaining the comic? [[Special:Contributions/172.68.23.81\|172.68.23.81]] 18:07, 23 December 2024 (UTC)
	:Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141\|172.69.136.141]] 18:43, 23 December 2024 (UTC)		:Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141\|172.69.136.141]] 18:43, 23 December 2024 (UTC)
		+	::Interesting, and it probably can do without saying the bit that is removed, but not for the reason given in the removal. As pointed out, above, practical timing issues don't depend upon the base computer being binary or not ("assume log-base-2 because computers are all binary" isn't really a useful argument). Some theoretical function creating and using a basic binary tree might (according to its operational needs) scale its operational speed by log-base-2 as a key factor, but a version that uses a k-d tree by log-base-k (you can imagine them being ultiately functionally equivalent by way of a Cantor-pairing(/tripling/etc) equivalence, if you want justification for this hypothetical choice between). They'd both be considered O(... log N ...), give or take any other accompanyting factors (or overriding terms). But you can't say that an O(... log N ...) solution will take a-specific-base-of-N multiple of time, certainy not base-2. [[Special:Contributions/172.70.58.45\|172.70.58.45]] 20:01, 23 December 2024 (UTC)

← Older revision		Revision as of 18:43, 23 December 2024
Line 114:		Line 114:
	Regarding {{diff\|360113\|this edit}}, I have my reservations. While Log<sub>2</sub> ''may'' be 'logical' in a system using binary, there's no reason why the algorithm cannot be implemented upon a trinary-based "machine code" system, or one in quad (and I actually have created a four-instruction 'ultra-RISC' microcode kernel, of sorts, that used base-4 principles, not base-2), or decimal/BCD, and then byte-size is commonly 8-bit with 16-bit, 32-bit and 64-bit extensions to the basic unit and ''could'' translate to an equivalent higher-base if you are bothered about ''n'' vs. log<sub>''x''</sub> ''n'' efficiency at lower ''n''s and higher ''x''s. Could even be natural-log (for reasons entirely unrelated to the hardware/firmware/software it is implemented on, just what it needs to do). Most of the time, we don't care if it's O(log<sub>10</sub> ''n'') or O(ln ''n'') or whatever, because the difference is an appropriate constant multiple. That's something generally not retained... we may have O(''m'' log ''n''), for independent variable ''m'', but something like O(2 log ''n'') is treated as O(log ''n'') equivalent, like O(2) is just O(1) in the final analysis, and why the O(1e8*n) reality sneaks through here as O(n). So, ''by actual implementation'', you can't actually say that O(''n'' log ''n'') will be gte O(''n'') always. With 1<''n''<log_base, it won't be. ...Whether or not we're free to consider either generality, though, I definitely won't ask you how algorithms actually stack up next to each other where run under ''n''=0 conditions! But at least O(''n''<sup>-1</sup>) isn't a common thing... ;) [[Special:Contributions/172.69.194.19\|172.69.194.19]] 18:01, 23 December 2024 (UTC)		Regarding {{diff\|360113\|this edit}}, I have my reservations. While Log<sub>2</sub> ''may'' be 'logical' in a system using binary, there's no reason why the algorithm cannot be implemented upon a trinary-based "machine code" system, or one in quad (and I actually have created a four-instruction 'ultra-RISC' microcode kernel, of sorts, that used base-4 principles, not base-2), or decimal/BCD, and then byte-size is commonly 8-bit with 16-bit, 32-bit and 64-bit extensions to the basic unit and ''could'' translate to an equivalent higher-base if you are bothered about ''n'' vs. log<sub>''x''</sub> ''n'' efficiency at lower ''n''s and higher ''x''s. Could even be natural-log (for reasons entirely unrelated to the hardware/firmware/software it is implemented on, just what it needs to do). Most of the time, we don't care if it's O(log<sub>10</sub> ''n'') or O(ln ''n'') or whatever, because the difference is an appropriate constant multiple. That's something generally not retained... we may have O(''m'' log ''n''), for independent variable ''m'', but something like O(2 log ''n'') is treated as O(log ''n'') equivalent, like O(2) is just O(1) in the final analysis, and why the O(1e8*n) reality sneaks through here as O(n). So, ''by actual implementation'', you can't actually say that O(''n'' log ''n'') will be gte O(''n'') always. With 1<''n''<log_base, it won't be. ...Whether or not we're free to consider either generality, though, I definitely won't ask you how algorithms actually stack up next to each other where run under ''n''=0 conditions! But at least O(''n''<sup>-1</sup>) isn't a common thing... ;) [[Special:Contributions/172.69.194.19\|172.69.194.19]] 18:01, 23 December 2024 (UTC)
	:What does this possibly have to do with explaining the comic? [[Special:Contributions/172.68.23.81\|172.68.23.81]] 18:07, 23 December 2024 (UTC)		:What does this possibly have to do with explaining the comic? [[Special:Contributions/172.68.23.81\|172.68.23.81]] 18:07, 23 December 2024 (UTC)
		+	:Hi, I made this edit. I removed that bit because it's too pedantic for an ExplainXKCD explanation, and in my opinion completely unnecessary. We don't need to explain Big-O, we need to explain the comic. In addition, while the math is strictly speaking true in that x>x*log<sub>a</sub>(x) when x<a, in computer science literature and discussion base-2 logs are typically assumed to be the default; if it isn't, it needs to be marked as such. Additionally the whole point of Big-O is growth: sure, that inequality holds when x is small, but <em>we're not interested in it being small</em>. As for ternary or whatever, those never come up. A few ternary machines existed in the 60s, sure, whatever, and occasionally someone experiments with something weird, but of the billions of computers that are in use, all are binary. So basically my message is to remember what forum we're speaking in. [[Special:Contributions/172.69.136.141\|172.69.136.141]] 18:43, 23 December 2024 (UTC)