Fibonacci Using DP in DSA Typescript - 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.

How does the time needed grow as we ask for bigger Fibonacci numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function fibonacciDP(n: number): number {
  const dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
    

This code calculates the nth Fibonacci number by building up from smaller results and storing them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each new Fibonacci number is found by adding two previous numbers, done once per step.

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 grows.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly in proportion to the size of n.

Common Mistake

[X] Wrong: "Calculating Fibonacci with DP is as slow as the simple recursive method because it still calls itself many times."

[OK] Correct: DP stores results and avoids repeated work, so it only does each calculation once, making it much faster.

Interview Connect

Understanding this helps you explain how saving past results speeds up problems that repeat work, a key skill in many coding challenges.

Self-Check

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