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 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")
- 10:34, 15 February 2023 Chandra (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [502 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: cannot find pdf of original paper or any description of the actual algorithm, but likely the same space as Chin's algorithm) == Description == == Approximate? == Approximate Approximation Factor: 2 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.worldcat.org/title/computing-matrix-chain-products-in-near-...")
- 10:34, 15 February 2023 Czumaj (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\log n)$ == Space Complexity == $O(n)$ words? (Derived: solving the optimal triangulation problem of a convex polygon where there are $n+1$ vertices and $n+1$, so total $O(n)$ auxiliary space) == Description == == Approximate? == Approximate Approximation Factor: 1.1547 == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?d...")
- 10:34, 15 February 2023 Dynamic Programming (Change-Making Problem Change-Making Problem) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Sn)$ == Space Complexity == $O(Sn)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == https://dl.acm.org/doi/10.1145/321864.321874")
- 10:34, 15 February 2023 Brute Force (Change-Making Problem Change-Making Problem) (hist | edit) [258 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(S^n)$ == Space Complexity == $O(n)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 10:34, 15 February 2023 Dynamic Programming (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 10:34, 15 February 2023 Brute Force (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [257 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:34, 15 February 2023 PMS (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm^{2} \sigma)$ == Space Complexity == $O(m^{2} n)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://ieeexplore.ieee.org/abstract/document/4359890")
- 10:34, 15 February 2023 Risotto (Motif Search Motif Search) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2})$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11682462_69")
- 10:34, 15 February 2023 Census (Motif Search Motif Search) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45078-8_5")
- 10:34, 15 February 2023 Mitra (Motif Search Motif Search) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://pubmed.ncbi.nlm.nih.gov/12169566/")
- 10:34, 15 February 2023 Speller (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2}/w)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337")
- 10:34, 15 February 2023 Perumalla and Deo (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ auxiliary words (constant number of arrays as outlined in algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 10:34, 15 February 2023 Kadane's Algorithm (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1982 == Reference == -")
- 10:34, 15 February 2023 Shamos (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [290 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(log n)$ auxiliary words (keep track of recursive maximums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == -")
- 10:34, 15 February 2023 Faster Brute Force (via x(L:U) = x(L:U-1)+x(U)) (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/doi/pdf/10.1145/358234.381162")
- 10:34, 15 February 2023 Grenander (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (storing precomputed cumulative sums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Brute Force (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Bringman (Subset Sum The Subset-Sum Problem) (hist | edit) [395 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(nt^{1+\epsilon})$ == Space Complexity == \tilde{O}(nt^\epsilon) (https://arxiv.org/abs/1610.04712) == Description == == Approximate? == Approximate Approximation Factor: (n+t)^{-\Omega(1)} error == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1610.04712")
- 10:34, 15 February 2023 Koiliaris and Xu (Subset Sum The Subset-Sum Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2019 == Reference == https://dl.acm.org/doi/pdf/10.1145/3329863")
- 10:34, 15 February 2023 Psinger (Subset Sum The Subset-Sum Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n max(S))$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349")
- 10:34, 15 February 2023 Bellman dynamic programming algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/nav.3800030107")
- 10:34, 15 February 2023 Horowitz and Sahni (Subset Sum The Subset-Sum Problem) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({2}^{(n/{2})$}) (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/321812.321823")
- 10:34, 15 February 2023 R-tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == R-Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(log n)$ (https://www.sciencedirect.com/science/article/pii/S1877050915019675, Table 2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf")
- 10:34, 15 February 2023 K-d Tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == k-d Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(n)$ (https://dl.acm.org/doi/pdf/10.1145/355744.355745) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://dl.acm.org/doi/pdf/10.1145/355744.355745")
- 10:34, 15 February 2023 Linear search (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: Only ever storing the current shortest distance and the corresponding node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference == -")
- 10:34, 15 February 2023 Zhao-Saalfeld ( Line Simplification) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: There is an auxiliary sleeve set that is $O(n)$ size worst-case) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.494.7321")
- 10:34, 15 February 2023 Lang simplification ( Line Simplification) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from a point in the search interval to the search line, which is all $O(1)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == -")
- 10:34, 15 February 2023 Opheim simplification ( Line Simplification) (hist | edit) [477 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == http://dx.doi.org/10.2312/eg.19811012")
- 10:34, 15 February 2023 Reumann–Witkam ( Line Simplification) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from the next point to the line.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference ==")
- 10:34, 15 February 2023 Visvalingam–Whyatt ( Line Simplification) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ (Derived: Storing each points effective area) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == https://hull-repository.worktribe.com/output/459275")
- 10:33, 15 February 2023 Ramer–Douglas–Peucker algorithm ( Line Simplification) (hist | edit) [421 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? (Derived: Recursive algorithm that has a worst-case recursion tree depth of O(n)?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0146664X72800170")
- 10:33, 15 February 2023 Long Multiplication ( Multiplication) (hist | edit) [289 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary bits (Easily derived (needed for intermediate results)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 10:33, 15 February 2023 Toom-3 ( Multiplication) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{4}6})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/3)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1969 == Reference == https://www.ams.org/journals/tran/1969-142-00/S0002-9947-1969-0249212-8/S0002-9947-1969-0249212-8.pdf")
- 10:33, 15 February 2023 Karatsuba Algorithm ( Multiplication) (hist | edit) [423 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{5}8})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/2)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1962 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng")
- 10:33, 15 February 2023 Rabin–Scott powerset construction ( NFA to DFA conversion) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ (Derived: besides the O(2^n) output nodes and the O(n) input nodes, there's nothing to store) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1959 == Reference == https://ieeexplore.ieee.org/document/5392601")