New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:36, 15 February 2023 Chan's algorithm (2-dimensional; 3-dimensional Convex Hull) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://link.springer.com/article/10.1007/BF02712873) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://link.springer.com/article/10.1007/BF02712873")
- 10:36, 15 February 2023 The ultimate planar convex hull algorithm (2-dimensional Convex Hull) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://ecommons.cornell.edu/handle/1813/6417) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://ecommons.cornell.edu/handle/1813/6417")
- 10:36, 15 February 2023 Andrew's algorithm (2-dimensional Convex Hull) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/pii/0020019079900723")
- 10:36, 15 February 2023 Preparata and Hong (2-dimensional; 3-dimensional Convex Hull) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=359430")
- 10:36, 15 February 2023 W. Eddy Quickhull (2-dimensional Convex Hull) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nh)$ == Space Complexity == $O(h)$? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=355766")
- 10:36, 15 February 2023 Graham (2-dimensional Convex Hull) (hist | edit) [345 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/pii/0020019072900452?via%3Dihub")
- 10:36, 15 February 2023 Goodrich (Reporting all intersection points, line segments Line segment intersection) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n))$ == Space Complexity == $O(n+k)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=72950")
- 10:36, 15 February 2023 Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection) (hist | edit) [398 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://dl.acm.org/citation.cfm?id=304991) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM, under more restrictions/considerations? (predicate arithmetic) == Year == 1999 == Reference == https://dl.acm.org/citation.cfm?id=304991")
- 10:36, 15 February 2023 Balaban. (Reporting all intersection points, generalized segments Line segment intersection) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/pdf/10.1145/220279.220302) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1995 == Reference == https://dl.acm.org/doi/pdf/10.1145/220279.220302")
- 10:36, 15 February 2023 Jean-Daniel Boissonnat and Franco P. Preparata. (Reporting all intersection points, generalized segments Line segment intersection) (hist | edit) [453 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( n log n + k log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/epdf/10.1137/S0097539797329373) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM, under more restrictions/considerations? (predicate arithmetic, exact arithmetic) == Year == 1997 == Reference == https://epubs.siam.org/doi/abs/10.1137/S0097539797329373")
- 10:36, 15 February 2023 NIEVERGELT. J.. AND PREPARATA (Section 3) (Reporting all intersection points, convex polygons Line segment intersection) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1982 == Reference == https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf")
- 10:36, 15 February 2023 CHAZELLE (Reporting all intersection points, line segments Line segment intersection) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( n*log^{2}(n)/(log log n) + k)$ == Space Complexity == $O(n+k)$ total (and possibly auxiliary as well?) words (https://www.sciencedirect.com/science/article/pii/0022000086900255) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0022000086900255")
- 10:36, 15 February 2023 Chazelle & Edelsbrunner (Reporting all intersection points, line segments Line segment intersection) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n+k)$ total? words (https://dl.acm.org/doi/10.1145/147508.147511) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/147508.147511")
- 10:36, 15 February 2023 Lee and Sidford ( Linear Programming) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((nnz(A) + n^{2}) n^{0.5})$ == Space Complexity == $O(nm+n^{2})$?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1503.01752")
- 10:36, 15 February 2023 Cohen; Lee and Song ( Linear Programming) (hist | edit) [706 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{max(omega, {2.5}-alpha/{2}, {13}/{6})}*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication; currently $O(n^{2.37285956})$ == Space Complexity == $O(nm+n^{2})$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://ar...")
- 10:36, 15 February 2023 Affine scaling ( Linear Programming) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == ? (originally $O(n^{3.5} L)$ but seems unclear) == Space Complexity == $O(nm+m^{2})$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == -")
- 10:36, 15 February 2023 Terlaky's Criss-cross algorithm ( Linear Programming) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m))$? (previously $O({2}^n)$) == Space Complexity == $O(nm)$ words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == -")
- 10:36, 15 February 2023 Simplex Algorithm ( Linear Programming) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m))$? (previously $O({2}^n)$) == Space Complexity == $O(nm)$ words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1947 == Reference == -")
- 10:36, 15 February 2023 Karmarkar's algorithm ( Linear Programming) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3.5} L^{2} logL loglogL)$ == Space Complexity == $O(nmL)$ words (can be derived from paper?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf")
- 10:36, 15 February 2023 Harrow (Quantum) (Sparse Linear System Linear System) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k^{2}*logn)$ == Space Complexity == $O(log n)$ qubits (https://arxiv.org/pdf/0811.3171.pdf) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 2009 == Reference == https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.103.150502")
- 10:36, 15 February 2023 Conjugate Gradient (Approximation? with positive definite matrix Linear System) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m k^{0.5})$ == Space Complexity == $O(m)$ words (http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1952 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf")
- 10:36, 15 February 2023 Byskov (4-Graph Coloring Graph Coloring) (hist | edit) [404 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7504}^n)$ == Space Complexity == $O(n^{2})$? words (can be derived from algo 89 plus the paper's algo for finding MIS's?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 10:36, 15 February 2023 Lawler (4-Graph Coloring Graph Coloring) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m + n)*{2}^n)$ == Space Complexity == $O(n+m)$ words ((can be easily derived; see section 6 of ref)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
- 10:36, 15 February 2023 Beigel & Eppstein (3-Graph Coloring Graph Coloring) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.3446}^n)$ == Space Complexity == $O(n^{2})$? words (can be derived from steps of algorithm? you add at most O(n^2) constraints, other info shouldn't take more than O(n^2) space, and you can reuse space during recursive steps) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnum...")
- 10:36, 15 February 2023 Schiermeyer (3-Graph Coloring Graph Coloring) (hist | edit) [385 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.415}^n)$ == Space Complexity == $O(nm+n^{2})$ loose bound, possibly $O(n+m)$? words ((can be derived from steps of algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://link.springer.com/chapter/10.1007/3-540-57899-4_51")
- 10:36, 15 February 2023 Lawler (3-Graph Coloring Graph Coloring) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*n*{3}^{(n/{3})}) ~ O(mn({1.445})^n)$ == Space Complexity == $O(n+m)$ words ((can be easily derived; see section 6 of ref)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
- 10:36, 15 February 2023 James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (st-Maximum Flow Maximum Flow) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Improvement of the KRT algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://dl.acm.org/citation.cfm?id=2488705")
- 10:36, 15 February 2023 Goldberg & Rao (Integer Maximum Flow Maximum Flow) (hist | edit) [385 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{1.5} Log(V^{2}/E) LogU)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Finding blocking flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181")
- 10:36, 15 February 2023 Phillips & Westbrook (st-Maximum Flow Maximum Flow) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE(Log(V;V/E)) + V^{2}(LogV)^{2} )$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://dl.acm.org/citation.cfm?id=167201")
- 10:36, 15 February 2023 King et al. (KRT) (st-Maximum Flow Maximum Flow) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{({2}+eps)})$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/citation.cfm?id=139438")
- 10:36, 15 February 2023 Alon (st-Maximum Flow Maximum Flow) (hist | edit) [430 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{({2.66})}LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/002001909090024R")
- 10:36, 15 February 2023 Cheriyan et al. (st-Maximum Flow Maximum Flow) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} / LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Uniform-Cost RAM (is this the same as Word RAM?) == Year == 1990 == Reference == https://link.springer.com/chapter/10.1007/BFb0032035")
- 10:36, 15 February 2023 Cheriyan & Hagerup (st-Maximum Flow Maximum Flow) (hist | edit) [436 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE*log(V))$ == Space Complexity == $O(V + E)$ words (Derived: d_heap and e_heap are size O(V). Adjacency list of a given vertex is O(V). Dynamic trees data structure is size O(E).) == Description == Push-relabel method == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/document/63465")
- 10:36, 15 February 2023 Ahuja & Orlin ( Maximum Flow) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{2}LogU)$ == Space Complexity == $O(ELogU)$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem")
- 10:36, 15 February 2023 Goldberg & Tarjan ( Maximum Flow) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELog(V^{2}/E))$ == Space Complexity == $O(E)$ words (can be derived? also hints of space complexity might be in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf")
- 10:36, 15 February 2023 Sleator & Tarjan ( Maximum Flow) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELogV)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 10:35, 15 February 2023 Cherkassky ( Maximum Flow) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E^{0.5})$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X")
- 10:35, 15 February 2023 Dinitz (with dynamic trees) ( Maximum Flow) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELogU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549")
- 10:35, 15 February 2023 Dantzig ( Maximum Flow) (hist | edit) [385 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}EU)$ == Space Complexity == $O(VE)$? words (can be derived? (assuming this is referring to simplex algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1951 == Reference ==")
- 10:35, 15 February 2023 Mukhopadhyay (LCS Longest Common Subsequence) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://www.sciencedirect.com/science/article/pii/0020025580900250) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0020025580900250")
- 10:35, 15 February 2023 Hunt and Szymanski (LCS Longest Common Subsequence) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://cse.hkust.edu.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf")
- 10:35, 15 February 2023 T. C. Hu ; M. T. Shing (Matrix Chain Ordering Problem Matrix Chain Multiplication) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://citeseerx.ist.psu.edu/viewdoc/citations?doi=10.1.1.695.2923")
- 10:35, 15 February 2023 Hashing (kth Order Statistic kth Order Statistic) (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: size of hashtable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 10:35, 15 February 2023 Spreadsort (Non-Comparison Sorting Sorting) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$? words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.semanticscholar.org/paper/The-Spreadsort-High-performance-General-case-Ross/41f5b49e9843b2d98b6b22a84924dae5761e6e52")
- 10:35, 15 February 2023 Burst Sort (Non-Comparison Sorting Sorting) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(wn)$ == Space Complexity == $O(wn)$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/citation.cfm?doid=1005813.1041517")
- 10:35, 15 February 2023 Bead Sort (Non-Comparison Sorting Sorting) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/~jaru003/research/publications/journals/beadsort.pdf")
- 10:35, 15 February 2023 Flash Sort (Non-Comparison Sorting Sorting) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == http://www.neubert.net/FSOIntro.html")
- 10:35, 15 February 2023 Naive sorting (Non-Comparison Sorting Sorting) (hist | edit) [262 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 10:35, 15 February 2023 Thorup's Sorting Algorithm (Comparison Sorting Sorting) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S0196677402912113?via%3Dihub")
- 10:35, 15 February 2023 Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log² n)$ == Space Complexity == $O({1})$? words (Paper claims "logspace uniform", so with O(log n) words, this is constant # of words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAC (shared-memory multiprocessor of the EREW PRAM variety) == Year == 1968 == Reference == https://epubs.siam.org/doi/abs/10.1137/0218014")