Ask HN: O(n^n) procedure?

[cao825]

I was discussing with some friends at work some of the worst algorithms (in terms of Big O), like Bogo Sort, Stooge Sort, etc... We were trying to think of how one could write a procedure with O(n^n) and all of our attempts ended up being infinite or much less than n^n.

I would imagine we just didn't think in the correct terms. Unfortunately, neither Google nor Wolframalpha were any help finding one from my searches.

Thanks!

[tgflynn]

If you think of an nxn matrix the set of all paths containing one element from each column has cardinality n^n. This is also the set of all functions from a set of cardinality n to itself or the set of all sequences of length n where each element is an element of a set of cardinality n.

Below is a procedure that generates it. The number of operations is actually sum from k =0 to k =n ( n^(n-k) ) but asymptotically that's still O( n^n ).

  def allFunctions( s, i = 0, count = 0 ):
 
    F = []
    if i == len( s ) - 1:
      return ( [ [ x ] for x in s ], len( s ) )
    (G,count) = allFunctions( s, i + 1, count )
    for g in G:
      for i in range( len( s ) ):
        F.append( g + [ s[i] ] )
        count += 1
    return ( F, count )

[cao825]

You rock.