Fibonacci Using DP in DSA C - Time & Space Complexity

Time Complexity: Fibonacci Using DP

O(n)

Understanding Time Complexity

We want to understand how fast the Fibonacci sequence calculation runs when using dynamic programming.

Specifically, how the number of steps grows as the input number increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int fibonacci(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
    

This code calculates the nth Fibonacci number by storing previous results to avoid repeated work.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 2 to n, calculating each Fibonacci number once.
• How many times: Exactly n-1 times, once for each number from 2 up to n.

How Execution Grows With Input

Each new Fibonacci number is calculated once using two previous results, so work grows steadily with n.

Input Size (n)	Approx. Operations
10	About 8 additions
100	About 98 additions
1000	About 998 additions

Pattern observation: The number of operations grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the Fibonacci number grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "Calculating Fibonacci with recursion is always fast because it just calls itself."

[OK] Correct: Simple recursion repeats many calculations, making it much slower than this dynamic programming approach.

Interview Connect

Understanding how dynamic programming improves speed by saving past results is a key skill that shows you can optimize solutions thoughtfully.

Self-Check

"What if we changed the array to only store the last two Fibonacci numbers instead of all? How would the time complexity change?"