New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 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")
- 10:35, 15 February 2023 Shell Sort; (Sedgewick) (Comparison Sorting Sorting) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
- 10:35, 15 February 2023 Shell Sort; (Pratt) (Comparison Sorting Sorting) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log² n)$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
- 10:35, 15 February 2023 Shell Sort; (Frank & Lazarus) (Comparison Sorting Sorting) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
- 10:35, 15 February 2023 Shell Sort; (Shell) (Comparison Sorting Sorting) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
- 10:35, 15 February 2023 Cube Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0196677492900166?via%3Dihub")
- 10:35, 15 February 2023 Tim Sort (Comparison Sorting Sorting) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == -")
- 10:35, 15 February 2023 Quick Sort (Comparison Sorting Sorting) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O(logn)$ words (https://academic.oup.com/comjnl/article/5/1/10/395338?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf")
- 10:35, 15 February 2023 Tree sort (Comparison Sorting Sorting) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.neubert.net/FSOIntro.html")
- 10:35, 15 February 2023 Bitap algorithm (Single String Search String Search) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses a bit array of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://en.wikipedia.org/wiki/Bitap_algorithm")
- 10:35, 15 February 2023 Bunch; Hopcroft (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{37}6})$ == Space Complexity == $\tilde{O}(n^{2})$ words (Derived: Uses Strassen multiplication and a constant number of $n \times n$ auxiliary matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/citation.cfm?id=248979")
- 10:35, 15 February 2023 Khuller; Matias Randomized Sieve ( Closest Pair Problem) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$, not sure if this is auxiliary not mentioned (https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://dl.acm.org/citation.cfm?id=207181")
- 10:35, 15 February 2023 Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring) (hist | edit) [654 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7272}^n)$ == Space Complexity == $O(n)$ words (Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity) == Description == == Approximate? == Exac...")
- 10:35, 15 February 2023 Petford and Welsh (3-Graph Coloring Graph Coloring) (hist | edit) [465 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: we store the coloring of each vertex in a dictionary and the maximum size of this dictionary is equal to the number of vertices in the graph, n.) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0012365X89902148")
- 10:35, 15 February 2023 Rao-Blackwellized Particle Filtering SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words? ((based on Section 4 of the paper?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://papers.nips.cc/paper/1716-bayesian-map-learning-in-dynamic-environments.pdf")
- 10:35, 15 February 2023 Compressed Extended KF (SLAM Algorithms SLAM Algorithms) (hist | edit) [421 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.999&rep=rep1&type=pdf")
- 10:35, 15 February 2023 UKF (SLAM Algorithms SLAM Algorithms) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://www.seas.harvard.edu/courses/cs281/papers/unscented.pdf")
- 10:35, 15 February 2023 EKF SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == http://ais.informatik.uni-freiburg.de/teaching/ss12/robotics/slides/12-slam.pdf")
- 10:35, 15 February 2023 Image quilting Efros-Freeman (Texture Synthesis Texture Synthesis) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383296")
- 10:35, 15 February 2023 R. Paget ; I.D. Longstaff (Texture Synthesis Texture Synthesis) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://ieeexplore.ieee.org/abstract/document/679446")
- 10:35, 15 February 2023 Image analogies Hertzmann (Texture Synthesis Texture Synthesis) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N log n)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383295")
- 10:35, 15 February 2023 Non-parametric sampling Efros and Leung (Texture Synthesis Texture Synthesis) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/abstract/document/790383")
- 10:35, 15 February 2023 Petro Vlahos Algorithm (Image Compositing Image Compositing) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k/r)$ == Space Complexity == $O(nk)$?? words (Keeps track of all pixels across all images) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1985 == Reference ==")
- 10:35, 15 February 2023 Roth AlignACE (Motif Search Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: essentially just modified Gibbs sampling) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9788350")
- 10:35, 15 February 2023 Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/doi/pdf/10.1145/1150334.1150336")
- 10:35, 15 February 2023 Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem) (hist | edit) [455 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn^{2})$ == Space Complexity == $O(dm)$ (Derived -- worst case, updating each set in S to be something else and we don't want to change the input) == Description == == Approximate? == Approximate Approximation Factor: ln n - lnln n + \Theta(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1979 == Reference == https://www.jstor.org/stable/3689577#metadata_info_tab_contents")
- 10:35, 15 February 2023 The SUSAN corner detector ( Corner Detection) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
- 10:35, 15 February 2023 L. Kitchen and A. Rosenfeld (Grey-scale Corner Detection) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0167865582900204")
- 10:34, 15 February 2023 Harris and Stephens algorithm ( Corner Detection) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == http://www.bmva.org/bmvc/1988/avc-88-023.pdf")
- 10:34, 15 February 2023 Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} loglogE)$ == Space Complexity == $O(V)$? memory cells (Derived: One memory cell per tunnel-city pair, with one tunnel total) == Description == Tunneling == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/876638.876640")
- 10:34, 15 February 2023 Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == $O({2}^V)$ words (http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == https://doi.org/10.1287/opre.2.4.393")
- 10:34, 15 February 2023 Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $exp(V)$ == Space Complexity == $O(V^{4})$ words (Derived: V^2 + 2V constraints on V^2 variables, most integer programs use space of O(nm) where n=#vars and m=#constraints) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/doi/10.1145/321043.321046")
- 10:34, 15 February 2023 Micali and Vazirani ( Maximum Cardinality Matching) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(V)$ not mentioned (https://link.springer.com/content/pdf/10.1007/PL00009186.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Restricted Randomness (RR) == Year == 1980 == Reference == https://dl.acm.org/doi/10.1109/SFCS.1980.12")
- 10:34, 15 February 2023 Brélaz (DSatur) (3-Graph Coloring Graph Coloring) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V + E)$ words (Derived using adjacency lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359094.359101")
- 10:34, 15 February 2023 Karger, Blum ( Graph Coloring) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(poly(V))$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: $\tilde{O}(n^{3/14})$ == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204")
- 10:34, 15 February 2023 Schonhage's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032")
- 10:34, 15 February 2023 Bini's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{779}9})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: $O(n logn)$ error == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://doi.org/10.1016/0020-0190(79)90113-3")
- 10:34, 15 February 2023 Chin (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.) == Description == == Approximate? == Approximate Approximation Factor: 1.2485 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://dl.acm.org/citation.cfm?id=359556")