# Algorithms with polynomial time complexity of higher order

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

• 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.
– mrk
Apr 3, 2013 at 18:23
• Have a look at Polynomial-time algorithms with huge exponent/constant on CSTheory.
– Juho
Apr 3, 2013 at 18:27
• 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). Apr 3, 2013 at 18:47
• 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".) Apr 3, 2013 at 20:57
• 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. Apr 10, 2013 at 22:37

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.
• @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)$. Apr 4, 2013 at 6:15