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.
Loading...
Related Quiz
- DFS explores as _______ as possible before backtracking.
- The Fibonacci sequence starts with the numbers 0 and _______.
- Which data structure is typically used to implement binary search efficiently?
- Recursion relies on the stack's _______ behavior to manage function calls and their respective _______.
- Binary search operates by repeatedly dividing the _______ in half until the desired element is found or determined to be absent.