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.)

Improve this question
$\endgroup$
7
  • 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$
    – mrk
    Apr 3, 2013 at 18:23
  • 8
    $\begingroup$ Have a look at Polynomial-time algorithms with huge exponent/constant on CSTheory. $\endgroup$
    – Juho
    Apr 3, 2013 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, 2013 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, 2013 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, 2013 at 22:37

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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, 2013 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, 2013 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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