Problem Detail: At the Wikipedia article on time complexity, only a PRAM example is given for polylogarithmic time. Let $T(n)$ denote the largest number of steps used by a machine to reach a final state on any input with size $n$ bits.
Is there a program for a standard sequential model of computation (e.g. a Turing machine or a sequential random-access machine), solving some natural problem, so that $T(n) in Theta((log n)^k)$ for some fixed $k>1$?
Asked By : András Salamon
Answered By : Realz Slaw
Where each operation is $ Oleft(log^knright)$ amortized/expected; I don’t know if necessarily $Thetaleft(log^knright)$:
- Dynamic graph connectivity algorithms
- Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity (PDF)
- Dynamic graph connectivity in polylogarithmic worst case time (PDF, slides)
- Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation (PDF)
- Lists of connectivity problems
- Maintaining Dynamic Sequences under Equality Tests in Polylogarithmic Time (PDF)
- Distances and point-sets:
- Maintaining the miminal distance of a point set in polylogarithmic time (PDF, $Oleft(log^2nright)$, Smid)
- New techniques for some dynamic closest-point and farthest-point problems ($Oleft(log^D nright)$ Supowit)
- New Techniques For Exact And Approximate Dynamic Closest-Point Problems (PDF, Kapoor, Smid, $Oleft(log^D n log log nright)$, though cites others with just $O(polylog)$)
- TOPP 63: Dynamic Planar Nearest Neighbors, lists 3 papers with data structures that have operations that run in $Oleft(log^k nright)$ time
- Point location algorithms,
- Monotone subdivisions, without fractional cascading, query-time is $Oleft(log^2 nright)$
- Best known algorithms for point-location in higher-dimensions ($gt 2$) have a trade-off; $Oleft(log nright)$ query-time has large memory requirements that make them unscaleable. Reducing the memory requirements (for example to $Oleft(nlog nright)$ results in query-times of $Oleft(log^k nright)$
- Efficient Partition Trees (PDF, Matousek, $Oleft(log^2 nright)$ insertion time)
- An Implicit Data Structure For The Dictionary Problem That Runs In Polylog Time (Munro, $Oleft(log^2nright)$)
There are also many algorithms with polylogarithmic factors; $tilde {O}(cdot)$ is notation that is used when hiding polylogarithmic factors. So $Oleft(nlog^k n right)intilde {O}(n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16622
