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