4
$\begingroup$

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting.

  • Linear Search - with time complexity $O(n)$

  • Matrix Addition - with time complexity $O(n^2)$

  • Matrix Multiplication - with time complexity $O(n^3)$

Is there any algorithm with a higher complexity like $n^4$, $n^5$ etc? I would like to know about practical algorithms with polynomial time complexity only.

(I am familiar with algorithms having exponential complexity and class NP algorithms. My doubt is not about them.)

$\endgroup$
  • 1
    $\begingroup$ Practical with higher order! I don't think so. But there are polytime algorithms with a 1000 or 2000 or even more in the exponent. $\endgroup$ – saadtaame Apr 3 '13 at 18:23
  • 8
    $\begingroup$ Have a look at Polynomial-time algorithms with huge exponent/constant on CSTheory. $\endgroup$ – Juho Apr 3 '13 at 18:27
  • 1
    $\begingroup$ Is your question about practical algorithms, or algorithms for practical problems? The two are very different. Furthermore, to call the complexity of (dense) matrix addition $O(n^2)$ might be construed as something of a misnomer; any algorithm doing (dense) matrix addition should take time proportional to the number of elements, and the input size - the matrices - will need space in the same proportion... so the complexity could justifiably be called $O(n)$ (where the problem size is the number of elements in the matrix). $\endgroup$ – Patrick87 Apr 3 '13 at 18:47
  • $\begingroup$ You mean $\Theta$ or $\Omega$, right? Also, define "practical". (Do you want to learn about algorithms or problems? I ask because there is no such thing as an "NP algorithm".) $\endgroup$ – Raphael Apr 3 '13 at 20:57
  • 2
    $\begingroup$ As pointed out in mathoverflow.net/questions/65412/… to decide if a convex hull in $d$-dimensional space is simplicial requires at least $\Omega(n \log n + n^{\lfloor d/2 \rfloor - 1})$ time. $\endgroup$ – András Salamon Apr 10 '13 at 22:37
9
$\begingroup$

The AKS primality test runs in time $\tilde{O}(n^6) \subseteq O(n^7)$, $n$ the length of the input number (in binary). This is the best known bound; as far as I know, there is no proven lower bound.

$\endgroup$
  • 1
    $\begingroup$ On the other hand, there is no reason to use AKS. You should use one of the probabilistic tests instead, with a probability of failure smaller than hardware failure. $\endgroup$ – Yuval Filmus Apr 3 '13 at 21:18
  • 1
    $\begingroup$ @YuvalFilmus True, but that is probably the case for any algorithm with runtime in $\omega(n^3)$ in practice, and in some settings for all algorithms with runtime in $\Omega(n)$. $\endgroup$ – Raphael Apr 4 '13 at 6:15

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.