Oh-notation above cubic

Question

I have a question about calculating time-complexity in algorithms. Is it possible to have a notation such as O(n^4) if you have four nested for-loops?

Answer 1

Quite simply, the answer is yes. Four nested loops could (depending on the loops) be O(n⁴).

There are not a lot of polynomial-time algorithms with complexity above cubic, but they do exist. For example, the well-known AKS primality test is O(k¹²) in its original formulation (where k is the length of the input number), though it has been recently reduced to k^7.5.