Question

    The Fibonacci sequence (F(n) = F(n-1) + F(n-2)) is a

    classic example demonstrating the benefits of Dynamic Programming. Without DP, a naive recursive solution suffers from:
    A Stack overflow for small 'N'. Correct Answer Incorrect Answer
    B High space complexity due to large array storage. Correct Answer Incorrect Answer
    C Recomputing the same subproblems multiple times. Correct Answer Incorrect Answer
    D Inability to handle negative numbers. Correct Answer Incorrect Answer
    E Incorrect results for large 'N'. Correct Answer Incorrect Answer

    Solution

    A naive recursive implementation of Fibonacci (e.g., fib(n) = fib(n-1) + fib(n-2)) repeatedly calculates the same Fibonacci numbers. For example, fib(5) calls fib(4) and fib(3). fib(4) then calls fib(3) and fib(2). Notice fib(3) is computed twice. This leads to exponential time complexity due to overlapping subproblems. Dynamic Programming (memoization or tabulation) solves this by storing and reusing computed values.

    Practice Next
    More IT Operating System Questions
    ask-question