New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 100 | older 100) (20 | 50 | 100 | 250 | 500)
- 12:18, 15 February 2023 Reduction from GeomBase to Visibility Between Segments (hist | edit) [455 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Visibility Between Segments == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Strips Cover Box to Point Covering (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: Strips Cover Box TO: Point Covering == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Triangles Cover Triangle to Triangle Measure (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Triangle Measure == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Hole in Union to Triangles Cover Triangle (hist | edit) [457 bytes] Admin (talk | contribs) (Created page with "FROM: Hole in Union TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Strips Cover Box to Triangles Cover Triangle (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Strips Cover Box TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Triangles Cover Triangle to Hole in Union (hist | edit) [457 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Hole in Union == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Strips Cover Box (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Strips Cover Box == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Separator2 (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Separator2 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Separator1 (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Separator1 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM to 3 Points on Line (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: 3 Points on Line == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3 Points on Line to Point on 3 Lines (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "FROM: 3 Points on Line TO: Point on 3 Lines == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM' to GeomBase (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: GeomBase == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to 3SUM' (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM' to 3SUM (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: 3SUM == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Partial Match to OV (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "FROM: Partial Match TO: OV == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt")
- 12:18, 15 February 2023 Reduction from CNF-SAT to Frechet Distance (hist | edit) [495 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Frechet Distance == Description == == Implications == If: to-time: $O({2}^{({2}-\epsilon)}$ for any $\epsilon > {0}$<br/>Then: from-time: $O({2}^{({1}-\delta/{2})N}$ where $N$ is s.t there are $n=\tilde{O}({2}^{N/2})$ vertices on each curve == Year == 2014 == Reference == Karl Bringmann, Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails https://people.mpi-inf.mpg.de/~kbringm...")
- 12:18, 15 February 2023 Reduction from OV to Partial Match (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Partial Match == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt")
- 12:18, 15 February 2023 Reduction from 3SUM to 3SUM' (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from UOV to Longest Common Subsequence (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "FROM: UOV TO: Longest Common Subsequence == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf")
- 12:18, 15 February 2023 Reduction from UOV to Dynamic Time Warping (hist | edit) [294 bytes] Admin (talk | contribs) (Created page with "FROM: UOV TO: Dynamic Time Warping == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf")
- 12:18, 15 February 2023 Reduction from OV to Edit Distance (hist | edit) [536 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Edit Distance == Description == == Implications == If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>Then: from-time: $O(d^(O({1})*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors == Year == 2014 == Reference == Backurs, Arturs, and Piotr Indyk. "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)." Proceedings of the forty-seventh annual ACM symposium on Theo...")
- 12:18, 15 February 2023 Reduction from OV to Diameter 2 vs 3 (hist | edit) [506 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Diameter 2 vs 3 == Description == == Implications == If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$<br/>Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://peop...")
- 12:18, 15 February 2023 Reduction from 3-OV to Diameter 3 vs 7 (hist | edit) [469 bytes] Admin (talk | contribs) (Created page with "FROM: 3-OV TO: Diameter 3 vs 7 == Description == == Implications == If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ == Year == 2018 == Reference == Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. https://dl.acm.org/doi/pdf/10.1145/3188745.3188950")
- 12:18, 15 February 2023 Reduction from CNF-SAT to k-OV (hist | edit) [466 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: k-OV == Description == == Implications == If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set<br/>Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses == Year == 2005 == Reference == Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 2005.")
- 12:18, 15 February 2023 Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/doi/abs/10.1145/320557.320571")
- 12:18, 15 February 2023 Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == poly-time == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/abs/10.1145/582318.582337")
- 12:18, 15 February 2023 Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k^{2} n^{2})$ == Space Complexity == $O(k^{2})$ words (Derived: Uses an auxiliary array of size $k \times k$) == Description == Multiway Decomposition Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://dl.acm.org/doi/abs/10.1145/319540.319546")
- 12:18, 15 February 2023 Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == Synthesis Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.vldb.org/conf/1983/P186.PDF")
- 12:18, 15 February 2023 Global Newton Method (n player games Nash Equilibria) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2008 == Reference == https://www.sciencedirect.com/science/article/pii/S0022053108000811")
- 12:18, 15 February 2023 Mixed Integer Programming (n player games Nash Equilibria) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2005 == Reference == https://www.aaai.org/Papers/AAAI/2005/AAAI05-078.pdf")
- 12:18, 15 February 2023 Support enumeration and search (n player games Nash Equilibria) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2004 == Reference == https://www.aaai.org/Library/AAAI/2004/aaai04-105.php")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{ck^{2} log (k^{2}n)$/eps^2}) == Space Complexity == $O(k^{2}log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method (2 player games Nash Equilibria) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{c log n/eps^2})$ == Space Complexity == $O(log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Search) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown? == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.semanticscholar.org/paper/A-Continuation-Method-for-Nash-Equilibria-in-Games-Blum-Shelton/4a3b80041922298db147debc2a2307bc4a5a42e9")
- 12:18, 15 February 2023 Tango Tree ( Self-Balancing Trees Search) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((k+{1})$log(log(n))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf")
- 12:18, 15 February 2023 Lemke-Howson Algorithm (2 player games Nash Equilibria) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Exponential == Space Complexity == $O(mn)$? words (I am not sure if this can be optimized?) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1964 == Reference == https://doi.org/10.1137/0112033")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Search) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Search) (hist | edit) [264 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Search) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Deletion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Deletion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Deletion) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Insertion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Insertion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Deletion) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Insertion) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Insertion) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Insertion) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Creation) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Creation) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Tango Tree ( Self-Balancing Trees Creation) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf")
- 12:18, 15 February 2023 Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + $O({1})$}) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 Babai 1980 (Graph Isomporhism, Trivalent Graphs Graph Isomorphism Problem) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(cn^{\frac{1}{2}} \log n) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 Gronlund, Pettie (3-Clique Exact-Weight k-Clique Problem) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}*(log log n)$^{2}/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Nesetril, Poljak (k-Clique k-Clique Problem) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication == Space Complexity == $O(n^({2}k/{3})$) ish words (matrix sizes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf")
- 12:18, 15 February 2023 APSP algorithm (3-Clique Min-Weight k-Clique Problem) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / {2}^(log n)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Brute force enumeration (k-Clique k-Clique Problem) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vertices we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Reduction to Chan, Williams (k-OV Orthogonal Vectors) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Chan, Williams (OV Orthogonal Vectors) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Abboud, Williams, Yu (OV Orthogonal Vectors) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 Reduction to Abboud, Williams, Yu (k-OV Orthogonal Vectors) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 Exhaustive search (Minimum Wiener Connector problem Wiener Index) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^($O(n)$) == Space Complexity == $O(n)$ auxiliary words (Keeps track of current subset being checked, minimum subset, and O(1) Wiener indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:18, 15 February 2023 Exhaustive search (k-OV Orthogonal Vectors) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vectors we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Wen (2-dimensional Maximum subarray problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016781919400063G")
- 12:18, 15 February 2023 KALYAN PERUMALLA and NARSINGH DEO (2-dimensional Maximum subarray problem) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Takaoka (2-dimensional Maximum subarray problem) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub")
- 12:18, 15 February 2023 Tamaki, Tokuyama (exact) (2-dimensional Maximum subarray problem) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Tamaki, Tokuyama (approximate) (2-dimensional Maximum subarray problem) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(omega)$ * (-log(epsilon))/epsilon) == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: (1-epsilon) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Smith (2-dimensional Maximum subarray problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(log n)$ auxiliary? words (divide-and-conquer) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0167642387900347")
- 12:18, 15 February 2023 Bentley (2-dimensional Maximum subarray problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ auxiliary? words ((i think you need to pre-process to get cumulative sums in each row?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/pdf/10.1145/1968.381154")
- 12:18, 15 February 2023 Brute force (2-dimensional Maximum subarray problem) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{6})$ == 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 RAM == Year == 1977 == Reference == -")
- 12:18, 15 February 2023 Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+({1.2906})$^k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://mediatum.ub.tum.de/doc/1094228/file.pdf")
- 12:18, 15 February 2023 Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/69332/eth-4359-01.pdf")
- 12:18, 15 February 2023 Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [453 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k k^{2}+kn)$ == Space Complexity == $O(k^{2})$ auxiliary? words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 12:18, 15 February 2023 Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+{2}^k k^{2})$ == Space Complexity == $O(k^{2})$ auxiliary words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.7270&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Chan (Real 3SUM 3SUM) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2018 == Reference == https://dl.acm.org/doi/abs/10.1145/3363541")
- 12:18, 15 February 2023 Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n, k)$) (i.e. (n, k) binomial coefficient) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:18, 15 February 2023 Freund (Real 3SUM 3SUM) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://link.springer.com/article/10.1007/s00453-015-0079-6")
- 12:18, 15 February 2023 Gronlund, Pettie (Real 3SUM 3SUM) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/((log n)$/(log log n))^{2}/{3}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1007/s00453-007-9036-3")
- 12:18, 15 February 2023 Kazuhisa Makino, Takeaki Uno; Section 6 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(delta^{4})$ == Space Complexity == $O(n+m)$ auxiliary(?) words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
- 12:18, 15 February 2023 Textbook Sort-and-Two-Sided-Traversal (Integer 3SUM 3SUM) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Textbook Sort-and-Binary-Search (Integer 3SUM 3SUM) (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(h)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.schoolofhaskell.com/user/edwardk/online-lca")
- 12:18, 15 February 2023 Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(n)$ words (https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439")
- 12:18, 15 February 2023 Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+log(n)$) == Space Complexity == $O(n)$ total (auxiliary?) words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 12:18, 15 February 2023 Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 12:18, 15 February 2023 Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [487 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e...")
- 12:18, 15 February 2023 Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(log(n))) == Space Complexity == $O(n*log(log(n)$)) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Brent-Dekker Method (General Root Computation Root Computation) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 ==...")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [354 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(n)) == Space Complexity == $O(n*log(n)$) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Inverse quadratic interpolation (General Root Computation Root Computation) (hist | edit) [490 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?)...")