# Are there any exponential-time iterative algorithms?

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.

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.

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

• Thanks for your reply. But just to make sure: is there a recursive call when you write "for each tuple y in permutations(S')?" Because the question was about iterative algorithms – Yousuf Nov 4 '14 at 22:30
• Yes that is a recursive call. – Giovanni Botta Nov 4 '14 at 22:56