0

If there is a theory existing that proves this, what is it to prove that both would give the same worst case time complexity? It has been showed that both can provide solutions to a problem, but nothing about both giving same worst case time complexity.

jakepaul
  • 1
  • 1
    Does this answer your question? [Do iterative and recursive versions of an algorithm have the same time complexity?](https://stackoverflow.com/questions/8532142/do-iterative-and-recursive-versions-of-an-algorithm-have-the-same-time-complexit) –  May 31 '20 at 19:55
  • A recursive algorithm can always be translated into an iterative algorithm by emulating the call-stack in the code. This only adds constant overhead, so the worst case complexity doesn't change in that case. The opposite can of course also be done, though not as easily. But in general you can translate any solution of one kind to one of the other. As long as the underlying algorithm is the same there shouldn't be any change beyond constant factors. –  May 31 '20 at 20:03
  • I see, thank you. very much. – jakepaul May 31 '20 at 20:10

1 Answers1

2

It completely depends on the problem. But generally, recursive solutions can be made more time-efficient by using dynamic programming.

cgDude
  • 93
  • 1
  • 8