All public logs

Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 11:19, 15 February 2023 Admin talk contribs created page Reduction from Triangle Collection* to dynamic 4/3-Diameter (Created page with "FROM: Triangle Collection* TO: dynamic 4/3-Diameter == Description == == Implications == assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is...")
• 11:19, 15 February 2023 Admin talk contribs created page Reduction from OuMV to dynamic st-Maximum Flow (Created page with "FROM: OuMV TO: dynamic st-Maximum Flow == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on unweifghted directed graphs or weighted undirected graphs on $n$ nodes with amortized time $O(n^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to dia...")
• 11:19, 15 February 2023 Admin talk contribs created page Reduction from CNF-SAT to dynamic st-Maximum Flow (Created page with "FROM: CNF-SAT TO: dynamic st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to...")
• 11:19, 15 February 2023 Admin talk contribs created page Reduction from OuMv to Bipartite Graph MCM (Created page with "FROM: OuMv TO: Bipartite Graph MCM == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to d...")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from GeomBase to Visibility Between Segments (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Strips Cover Box to Point Covering (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Triangles Cover Triangle to Triangle Measure (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Hole in Union to Triangles Cover Triangle (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Triangles Cover Triangle to Hole in Union (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Strips Cover Box to Triangles Cover Triangle (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from GeomBase to Strips Cover Box (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from GeomBase to Separator2 (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from GeomBase to Separator1 (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3 Points on Line to Point on 3 Lines (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3SUM to 3 Points on Line (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3SUM' to GeomBase (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from GeomBase to 3SUM' (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3SUM' to 3SUM (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from OV to Partial Match (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3SUM to 3SUM' (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from Partial Match to OV (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from UOV to Longest Common Subsequence (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from UOV to Dynamic Time Warping (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from CNF-SAT to Frechet Distance (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...")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from OV to Diameter 2 vs 3 (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...")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from OV to Edit Distance (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...")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from 3-OV to Diameter 3 vs 7 (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")
• 11:18, 15 February 2023 Admin talk contribs created page Reduction from CNF-SAT to k-OV (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.")
• 11:18, 15 February 2023 Admin talk contribs created page Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Global Newton Method (n player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Mixed Integer Programming (n player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Support enumeration and search (n player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Lipton, Markakis and Mehta method (2 player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Treap ( Self-Balancing Trees Search) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Tango Tree ( Self-Balancing Trees Search) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Lemke-Howson Algorithm (2 player games Nash Equilibria) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Search) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Search) (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 ==")
• 11:18, 15 February 2023 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Search) (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 ==")
• 11:18, 15 February 2023 Admin talk contribs created page Treap ( Self-Balancing Trees Deletion) (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")
• 11:18, 15 February 2023 Admin talk contribs created page AVL Tree ( Self-Balancing Trees Search) (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 ==")
• 11:18, 15 February 2023 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Deletion) (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")
• 11:18, 15 February 2023 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) (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 ==")
• 11:18, 15 February 2023 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Deletion) (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 ==")
• 11:18, 15 February 2023 Admin talk contribs created page Treap ( Self-Balancing Trees Insertion) (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")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)