Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

Question

In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are

1. Constant time $\mathcal{O}(1)$: Ex sum of first $n$ numbers
2. Logarithmic time $\mathcal{O}(\log n)$: Ex binary searching a sorted list
3. Linear time $\mathcal{O}(n)$: Ex Searching an unsorted list
4. LogLinear time $\mathcal{O}(n\log n)$: Ex Merge Sort
5. Quadratic time $\mathcal{O}(n^2)$: Ex Bubble/Insertion/Selection Sort
6. (Rarely) Cubic time $\mathcal{O}(n^3)$: Ex Gaussian Elimination of a Matrix

However it can be shown that $$ \mathcal{O}(1)\subset \mathcal{O}(\log n)\subset \ldots \subset \mathcal{O}(n^3)\subset \mathcal{O}(n^4)\subset\mathcal{O}(n^5)\subset\ldots\subset \mathcal{O}(n^k)\subset\ldots $$

so it would be expected that there would be more well known problems that are in higher order time complexity classes, such as $\mathcal{O}(n^8)$.

What are some examples of algorithms that fall into these classes $\mathcal{O}(n^k)$ where $k\geq 4$?

Answer 1

Brute-force algorithms can be considered as a good example to achieve the mentioned running times (i.e. $\Omega(n^4)$).

Suppose given the sequence $\sigma=\langle a_1,a_2,\dots , a_n\rangle$ of real numbers, you want to find, if exists $k$ elements ($k\geq 4$, and $k$ is constant ) from $\sigma$ such that $$\sum_{i=1}^{k}a_i=0.$$

Obviously, a simple brute-force algorithm for this problem check all $\binom{n}{k}$ subsets of the input and detect whether the elements in at least one of them sum to $0$. If $k$ is a constant then $\binom{n}{k}=\Theta(n^k)$. For example if $k=10$ then the running time of your algorithm is $\Theta(n^{10}).$ Finally, you find algorithm for your desired running time.

Answer 2

The problem of $1$-processor gap scheduling of $n$ jobs has time complexity $O(n^7)$.

The paper is available here.

Answer 3

Most simple example gives nested cycles: we know that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.

Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.

Another examples Karmarkar's algorithm, AKS primality test