Talk:Galactic algorithm: Difference between revisions

Content deleted Content added

Revision as of 14:23, 25 April 2024 edit Johnsoniensis (talk \| contribs) Extended confirmed users 746,930 edits math ← Previous edit		Latest revision as of 14:51, 30 June 2025 edit undo AMWJ (talk \| contribs) 42 edits →Shannon is not an example: Reply Tag: Reply
(One intermediate revision by one other user not shown)
Line 1: {{WikiProject banner shell\|class=C\|1= {{WPWikiProject Mathematics}} \|priority=Low}} }} == Multiplication algorithm == Line 25 ⟶ 26: Shannon's coding example is not related to the scale of the input and therefore it is not a galactic algorithm. [[User:Fulldecent\|Full Decent]] ([[User talk:Fulldecent\|talk]]) 17:18, 5 October 2019 (UTC) :Agreed - a "galactic algorithm" should be impractical on human-sized problems: as the name implies - it's only worthwhile on "galactically-sized" problems. :In the Shannon coding example, this algorithm takes <math>O(2^n)</math>, which gets increasingly impractical as n gets galactic. In fact, at small n (e.g. n=1), this algorithm is quite reasonable. :There ''is'' likely a way to describe this problem as galactic in terms of the length of the message rather than n, and making n part of the constant (much as the paragraph on subgraphs does). But this paragraph on Shannon doesn't do that. [[User:AMWJ\|AMWJ]] ([[User talk:AMWJ\|talk]]) 14:51, 30 June 2025 (UTC) == AKS primality test? ==