Time complexity: Revision history

26 June 2024

• curprev 06:5706:57, 26 June 2024‎ Citation bot talk contribs‎ 41,818 bytes −13‎ Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 813/3850 undo

27 May 2024

• curprev 18:4018:40, 27 May 2024‎ Comp.arch talk contribs‎ 41,831 bytes +18‎ k-d tree undo Tag: 2017 wikitext editor

4 May 2024

• curprev 05:2105:21, 4 May 2024‎ David Eppstein talk contribs‎ 41,813 bytes +587‎ →‎Second definition: fix ref undo

21 April 2024

• curprev 17:4117:41, 21 April 2024‎ MrOllie talk contribs‎ m 41,226 bytes −9‎ Reverted 1 edit by 152.57.224.229 (talk) to last revision by D.Lazard undo Tags: Twinkle Undo
• curprev 17:3417:34, 21 April 2024‎ 152.57.224.229 talk‎ 41,235 bytes +9‎ (edit summary removed) undo Tags: Undo Reverted
• curprev 10:5210:52, 21 April 2024‎ D.Lazard talk contribs‎ 41,226 bytes −9‎ Reverted 1 edit by GavinDouch (talk) undo Tags: Twinkle Undo Reverted
• curprev 10:4610:46, 21 April 2024‎ GavinDouch talk contribs‎ 41,235 bytes +9‎ →‎Polynomial time undo Tags: Reverted Visual edit

20 April 2024

• curprev 05:4705:47, 20 April 2024‎ David Eppstein talk contribs‎ 41,226 bytes +32‎ Joos Ulrich Heintz undo

13 April 2024

• curprev 05:4905:49, 13 April 2024‎ Citation bot talk contribs‎ 41,194 bytes +18‎ Added hdl. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 2848/3124 undo

19 March 2024

• curprev 17:2117:21, 19 March 2024‎ Lockesdonkey talk contribs‎ 41,176 bytes 0‎ →‎Logarithmic time undo

18 March 2024

• curprev 03:2203:22, 18 March 2024‎ Citation bot talk contribs‎ 41,176 bytes +180‎ Add: isbn, doi-broken-date, hdl. | Use this bot. Report bugs. | Suggested by Abductive | Category:Analysis of algorithms | #UCB_Category 37/47 undo

14 March 2024

• curprev 20:5920:59, 14 March 2024‎ Lockesdonkey talk contribs‎ 40,996 bytes +415‎ →‎Logarithmic time: Clarify to make easier to understand to readers less familiar with math undo
• curprev 04:0804:08, 14 March 2024‎ CWenger talk contribs‎ m 40,581 bytes +1‎ missing space #article-section-source-editor undo Tags: Mobile edit Mobile app edit iOS app edit

1 March 2024

• curprev 05:4905:49, 1 March 2024‎ D.Lazard talk contribs‎ 40,580 bytes +6‎ Reverted 1 edit by 95.208.95.201 (talk) undo Tags: Twinkle Undo

29 February 2024

• curprev 21:4621:46, 29 February 2024‎ 95.208.95.201 talk‎ 40,574 bytes −6‎ We think thats wrong undo Tags: Reverted Visual edit

25 February 2024

• curprev 12:4712:47, 25 February 2024‎ 2a01:e0a:d6b:e7f0:c2e0:8c38:e8d7:beed talk‎ 40,580 bytes +3‎ Title in the table: Time complexity instead of Running time undo

18 February 2024

• curprev 13:4313:43, 18 February 2024‎ Drbogdan talk contribs‎ 40,577 bytes −74‎ Reverted good faith edits by Johnwilliamstafford (talk): Rv possibly good faith edits - please discuss on the talk-page for WP:CONSENSUS from other editors - (possible WP:COI) - thanks. undo Tags: Twinkle Undo
• curprev 11:2611:26, 18 February 2024‎ Johnwilliamstafford talk contribs‎ 40,651 bytes +74‎ Time complexity in practice image added undo Tags: Reverted Visual edit

11 February 2024

• curprev 01:5601:56, 11 February 2024‎ Chaotic Enby talk contribs‎ m 40,577 bytes −17‎ Reverted edits by 2806:250:90E:BCF2:9437:1B34:E856:2DA5 (talk) (AV) undo Tags: AntiVandal Rollback
• curprev 01:5601:56, 11 February 2024‎ 2806:250:90e:bcf2:9437:1b34:e856:2da5 talk‎ 40,594 bytes +17‎ →‎Polylogarithmic time undo Tags: Reverted nowiki added

28 January 2024

• curprev 13:4713:47, 28 January 2024‎ Erel Segal talk contribs‎ 40,577 bytes −3,313‎ →‎Strongly and weakly polynomial time: Move stuff to Strongly-polynomial time undo Tag: Visual edit
• curprev 12:3912:39, 28 January 2024‎ Erel Segal talk contribs‎ 43,890 bytes +4‎ →‎Strongly and weakly polynomial time undo Tag: Visual edit
• curprev 11:1111:11, 28 January 2024‎ Erel Segal talk contribs‎ 43,886 bytes −319‎ No edit summary undo

4 December 2023

• curprev 19:2419:24, 4 December 2023‎ David Eppstein talk contribs‎ 44,205 bytes +24‎ →‎Polynomial time: we have a separate article on almost the same topic that should be much more prominently linked here undo
• curprev 07:4107:41, 4 December 2023‎ David Eppstein talk contribs‎ 44,181 bytes +31‎ →‎Quasi-polynomial time: main undo

3 December 2023

• curprev 02:0102:01, 3 December 2023‎ David Eppstein talk contribs‎ 44,150 bytes +81‎ →‎Quasi-polynomial time: quasi-polynomial growth undo

28 October 2023

• curprev 16:5816:58, 28 October 2023‎ B732 talk contribs‎ m 44,069 bytes −29‎ Reverted edits by 176.29.19.72 (talk) (HG) (3.4.12) undo Tags: Huggle Rollback
• curprev 16:5616:56, 28 October 2023‎ 176.29.19.72 talk‎ 44,098 bytes +29‎ →‎Superpolynomial time undo Tags: Reverted Mobile edit Mobile web edit

23 October 2023

• curprev 01:2601:26, 23 October 2023‎ David Eppstein talk contribs‎ 44,069 bytes −621‎ →‎Quasi-polynomial time: unsourced editorialization undo

22 October 2023

• curprev 19:0919:09, 22 October 2023‎ SvenSandberg talk contribs‎ 44,690 bytes +23‎ →‎Factorial time: Clarified derivation of upper bound for factorial undo Tags: Mobile edit Mobile web edit
• curprev 18:5818:58, 22 October 2023‎ SvenSandberg talk contribs‎ 44,667 bytes +39‎ →‎Table of common time complexities undo Tags: Mobile edit Mobile web edit

14 October 2023

• curprev 21:2521:25, 14 October 2023‎ Zappymaxine talk contribs‎ m 44,628 bytes +10‎ more specificity for kd-tree example in time complexities undo Tag: Visual edit
• curprev 06:4206:42, 14 October 2023‎ SvenSandberg talk contribs‎ 44,618 bytes 0‎ →‎Table of common time complexities: Switched order of factorial and exponential (with polynomial exponent), so that the classes appear in increasing order. Factorial is 2^O(n log n). undo Tags: Mobile edit Mobile web edit

22 September 2023

• curprev 15:3115:31, 22 September 2023‎ 2600:1700:4ab0:5770:644:89df:ac62:6387 talk‎ 44,618 bytes +12‎ No edit summary undo Tags: Mobile edit Mobile web edit

11 September 2023

• curprev 16:1116:11, 11 September 2023‎ CRGreathouse talk contribs‎ m 44,606 bytes 0‎ →‎Sub-linear time: cleanup links, add link undo

9 September 2023

• curprev 20:1020:10, 9 September 2023‎ Hellacioussatyr talk contribs‎ 44,606 bytes −1‎ →‎Sub-linear time undo Tag: 2017 wikitext editor

9 August 2023

• curprev 08:5308:53, 9 August 2023‎ Citation bot talk contribs‎ 44,607 bytes +36‎ Alter: title, template type. Add: s2cid, chapter-url, date, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 2088/2306 undo

8 August 2023

• curprev 01:3701:37, 8 August 2023‎ David Eppstein talk contribs‎ 44,571 bytes −20‎ Undid revision 1169243847 by 102.67.246.8 (talk) not convinced that this is more clear rather than merely more wordy undo Tag: Undo

7 August 2023

• curprev 23:4223:42, 7 August 2023‎ 102.67.246.8 talk‎ 44,591 bytes +20‎ No edit summary undo Tag: Reverted

27 July 2023

• curprev 05:1505:15, 27 July 2023‎ 181.87.133.217 talk‎ 44,571 bytes −5‎ →‎Sub-exponential time: encyclopedic tone :3 undo

25 July 2023

• curprev 19:1319:13, 25 July 2023‎ Aviad.rubinstein talk contribs‎ 44,576 bytes −138‎ →‎Sub-linear time: Re-organized and cleaned this section. undo

18 July 2023

• curprev 22:5022:50, 18 July 2023‎ 68.48.13.7 talk‎ 44,714 bytes +1‎ →‎Constant time: Fixed a typo in the last line, a->at undo Tags: Mobile edit Mobile web edit

24 June 2023

• curprev 17:0517:05, 24 June 2023‎ David Eppstein talk contribs‎ 44,713 bytes −2‎ Undid revision 1161697295 by 192.114.91.215 (talk) unnecessary, because anything with that time bound is also in the time bound with the exponent rounded up to an integer undo Tag: Undo
• curprev 12:4512:45, 24 June 2023‎ 192.114.91.215 talk‎ 44,715 bytes +2‎ Things like DTIME(2^(0.5*c)) should also be considered to being in E. undo Tag: Reverted

8 June 2023

• curprev 16:4416:44, 8 June 2023‎ Danstronger talk contribs‎ 44,713 bytes −31‎ →‎Strongly and weakly polynomial time: Clarified explanation about pseudo polynomial time undo Tags: Mobile edit Mobile web edit
• curprev 07:2707:27, 8 June 2023‎ 2600:4040:a15d:e300:55bc:fd00:ba79:24f talk‎ 44,744 bytes −585‎ →‎Crazy redundancy undo

5 June 2023

• curprev 17:0517:05, 5 June 2023‎ Quantumly talk contribs‎ 45,329 bytes 0‎ Wrote Z+ instead of R+ accidentally. undo Tags: Visual edit Mobile edit Mobile web edit
• curprev 16:1116:11, 5 June 2023‎ Quantumly talk contribs‎ 45,329 bytes +2‎ Problems like Integer factorization which take time roughly O(2^(n^(1/3))) should be considered exponential time. This is because the class EXPTIME does admit problems taking DTIME(2^(n^k)) for 0< k < 1. In fact, a way to see this is by looking at NP-complete problems such as Dominating set problem on planar graphs, or the Planar 3 Coloring problem, which take "sub-exponential" time by the second definition and realize that it is unknown whether NP = EXPTIME. undo Tags: Visual edit Mobile edit Mobile web edit

30 May 2023

• curprev 11:3811:38, 30 May 2023‎ Renewal6 talk contribs‎ 45,327 bytes −45‎ Reverting edit(s) by 166.196.93.51 (talk) to rev. 1153965347 by 46.98.227.133: non-constructive (RW 16.1) undo Tags: RW Undo
• curprev 11:3411:34, 30 May 2023‎ 166.196.93.51 talk‎ 45,372 bytes +45‎ Nothing undo Tags: Reverted Mobile edit Mobile web edit