Tabulation Bottom Up DP in DSA Typescript - Time & Space Complexity

Time Complexity: Tabulation Bottom Up DP

O(n)

Understanding Time Complexity

We want to understand how the time needed grows when using tabulation in bottom-up dynamic programming.

Specifically, how the number of steps changes as the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function fib(n: number): number {
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 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 using bottom-up tabulation.

Identify Repeating Operations

• Primary operation: The for-loop that fills the dp array from 2 to n.
• How many times: It runs exactly n-1 times, once for each number from 2 up to n.

How Execution Grows With Input

As n grows, the loop runs more times, increasing the steps linearly.

Input Size (n)	Approx. Operations
10	About 9 additions
100	About 99 additions
1000	About 999 additions

Pattern observation: The number of steps grows roughly in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Dynamic programming always takes exponential time because it solves many subproblems."

[OK] Correct: Tabulation solves each subproblem once in order, so it only takes linear time here, not exponential.

Interview Connect

Understanding how tabulation reduces repeated work helps you explain efficient solutions clearly and confidently.

Self-Check

"What if we used recursion with memoization instead of tabulation? How would the time complexity change?"