Algorithms with polynomial time complexity of higher order

Problem Detail: 

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

Asked By : Deepu

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10997