Are there any exponential-time iterative algorithms?

Question

Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically.

The way I was thinking was to iterate not by adding 1, but by adding a small number j at the end of each loop. So the 3rd parameter in the for-loop would look like i+j instead of i++, and j would be really small (negative exponent perhaps? Like 2^-n)... Still, I'm not sure how such an algorithm could actually work, though.

Thanks for any input.

Answer 1

Yes. Given an input of length $n$, overwrite it and use the space to count to $2^n$ in binary.

Once you've done that, you could write out $2^n$ zeroes and then count to $2^{2^n}$ and so on, ad infinitum.

Answer 2

Many combinatorial algorithms can be implemented recursively and usually have exponential time complexity. For example, if S is a set, all the possible permutations of the elements in S can be computed using the following:

permutations(S): list[tuples] {
  c = an empty list of tuples
  for each x in S
    S' = S \ x
    for each tuple y in permutations(S')
      x.append([x, y])
  return c
}

where the notation combinations(S): list[tuples] means that the method returns a list of tuples and the notation [x, y] represents the concatenation of the element x (or the one element tuple x) and the tuple y and indentation indicates nesting. The code above is actually O(n!) which if I'm not mistaken is actually > O(2^n).