0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Yousuf Nov 4 '14 at 22:30
  • $\begingroup$ Yes that is a recursive call. $\endgroup$ – Giovanni Botta Nov 4 '14 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.