What is the time complexity of generating the nth Fibonacci number using a recursive approach?

  • O(2^n)
  • O(log n)
  • O(n)
  • O(n^2)
The time complexity of generating the nth Fibonacci number using a recursive approach is O(2^n). This is because the recursive algorithm without optimization recalculates the same Fibonacci numbers multiple times, leading to an exponential growth in the number of recursive calls.
Add your answer
Loading...

Leave a comment

Your email address will not be published. Required fields are marked *