Algorithms with polynomial time complexity of higher order

Question

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

• mrk: 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.
• Juho: Have a look at Polynomial-time algorithms with huge exponent/constant on CSTheory.
• Patrick87: 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).
• Raphael: 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".)
• András Salamon: 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.

Answer 1

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.

• Yuval Filmus: 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.
• Raphael: @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)$.