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:15, 15 February 2023 Admin talk contribs created page Cooper and Dasgupta algorithm ( Register Allocation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
• 11:15, 15 February 2023 Admin talk contribs created page Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(r)$ words (Derived: given the live ranges, the only auxiliary data structure is an "active" list that contains the active live ranges and this has length at most $r$) == Description == Greedy assignment == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Chow's Algorithm (Global Register Allocation Register Allocation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm also uses a register interference graph (RIG)) == Description == Assumes all variables allocated in main memory (i.e. assumes no spill handling required). Priority-based RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/502874.50...")
• 11:15, 15 February 2023 Admin talk contribs created page Chaitin's Algorithm (Global Register Allocation Register Allocation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors)) == Description == RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
• 11:15, 15 February 2023 Admin talk contribs created page Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(m)$ words (only keep track of m minimum values. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
• 11:15, 15 February 2023 Admin talk contribs created page Min/max sketches streaming algorithm (streaming Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O({1})$ words (only keep track of minimum value. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
• 11:15, 15 February 2023 Admin talk contribs created page HyperLogLog++ ( Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words ((see hyperloglog?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2014 == Reference == https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page HyperLogLog algorithm ( Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words (https://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2007 == Reference == http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page LogLog algorithm ( Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log(log(n)$)) words (http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Flajolet–Martin algorithm ( Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097915452) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1984 == Reference == http://algo.inria.fr/flajolet/Publications/src/FlMa85.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Naive solution ( Cardinality Estimation) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(n)$ words (keep track of exact histogram, may require storing all values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{4} log^{0.{1}.5}n)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://web.eecs.umich.edu/~fessler/papers/files/jour/94/web/fessler-94-...")
• 11:15, 15 February 2023 Admin talk contribs created page Α-EM algorithm ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1109/TIT.2002.808105")
• 11:15, 15 February 2023 Admin talk contribs created page Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://arxiv.org/abs/1709.06970")
• 11:15, 15 February 2023 Admin talk contribs created page Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == https://www.jstor.org/stable/2337481")
• 11:15, 15 February 2023 Admin talk contribs created page Newton–Raphson algorithm ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta guess, which is updated each iteration, and requires computation of the (inverse of the) Hessian matrix. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1685 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
• 11:15, 15 February 2023 Admin talk contribs created page Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
• 11:15, 15 February 2023 Admin talk contribs created page Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
• 11:15, 15 February 2023 Admin talk contribs created page Muller's method (General Root Computation Root Computation) (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}; 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 == 1956 == Reference == https://www.jstor.org/stable/200...")
• 11:15, 15 February 2023 Admin talk contribs created page Secant method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; 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 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Ridder's method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; 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 == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
• 11:15, 15 February 2023 Admin talk contribs created page Halley's method (Root Computation with continuous second derivative Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); 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 == Reference...")
• 11:15, 15 February 2023 Admin talk contribs created page Newton's method (Root Computation with continuous first derivative Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); 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 == Referenc...")
• 11:15, 15 February 2023 Admin talk contribs created page False position method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; 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 == 1690 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Bisection method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; 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 == 1820 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
• 11:15, 15 February 2023 Admin talk contribs created page Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
• 11:15, 15 February 2023 Admin talk contribs created page Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")
• 11:15, 15 February 2023 Admin talk contribs created page QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")
• 11:15, 15 February 2023 Admin talk contribs created page Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of $O(n)$-sized vectors per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1948 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu_i*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1921 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19210010104")
• 11:15, 15 February 2023 Admin talk contribs created page Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/129902.129906")
• 11:15, 15 February 2023 Admin talk contribs created page Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary words (Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/360767.360802")
• 11:15, 15 February 2023 Admin talk contribs created page Gupta-Sproull algorithm (Line Drawing Line Drawing) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == http://davis.wpi.edu/~matt/courses/clipping/")
• 11:15, 15 February 2023 Admin talk contribs created page Bresenham's line algorithm (Line Drawing Line Drawing) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1965 == Reference == https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Xiaolin Wu's line algorithm (Line Drawing Line Drawing) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1991 == Reference == http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf")
• 11:15, 15 February 2023 Admin talk contribs created page Digital Differential Analyzer (Line Drawing Line Drawing) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613")
• 11:15, 15 February 2023 Admin talk contribs created page Naive algorithm (Line Drawing Line Drawing) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (Created page with "== Time Complexity == $O(n(logn)$^{1.{58}5}) == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://ieeexplore.ieee.org/document/1926/")
• 11:15, 15 February 2023 Admin talk contribs created page Radix sorting method (General Permutations Generating Random Permutations) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Need to keep track of randomly generated numbers, but otherwise see radix sort) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1887 == Reference == -")

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