O(nⁿ) complexity pseuodocode structure using loops or recursion

O(n) time is simply one loop, O(n²) is a loop inside a loop where both loops run at kn times (k is an integer). The pattern continues. However, all finite integers k of O(nᵏ) can be constructed by hand that you can simply nest loops inside another, but what about O(nⁿ) where n is an arbitrary value that approaches infinity?

I was thinking a while loop would work here but how do we set up a break condition. Additionally, I believe O(nⁿ) complexity can be implemented using recursion but how would that look pseudocode-wise?

How do you construct a piece of algorithm that runs in O(nⁿ) using only loops or recursion?


A very simple iterative solution would be to calculate nn and then count up to it:

total = 1
for i in range(n):
    total *= n

for i in range(total):
    # Do something that does O(1) work

This could easily be rewritten recursively:

def calc_nn(n, k):
    if k == 0:
        return 1
    return n * calc_nn(n, k - 1)

def count_to(k):
    if k != 0:
        count_to(k - 1)

def recursive_version(n):
    count_to(calc_nn(n, n))