4
$\begingroup$

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$?

$\endgroup$
5
$\begingroup$

Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:

There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.

$\endgroup$
  • 1
    $\begingroup$ Is this a curated selection of some sort, and if so by which criteria? Or is it the result of a Google Scholar search? That is to say: I think an answer highlighting one problem/algorithm and explaining how the runtime comes about is more useful than a link farm. $\endgroup$ – Raphael Nov 2 '13 at 10:21
  • $\begingroup$ The last paragraph is not related to the question, but thanks for finding the others. $\endgroup$ – András Salamon Nov 8 '13 at 18:24
  • $\begingroup$ @AndrásSalamon I know, I was just mentioning it. $\endgroup$ – Realz Slaw Nov 8 '13 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.