patternMinor
Algorithms with polynomial time complexity of higher order
Viewed 0 times
orderpolynomialwithtimealgorithmshighercomplexity
Problem
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.)
-
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.)
Solution
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.
Context
StackExchange Computer Science Q#10997, answer score: 9
Revisions (0)
No revisions yet.