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

Time Complexity: Tabulation Bottom Up DP

O(n)

Understanding Time Complexity

We want to understand how fast a bottom-up dynamic programming solution runs as the input size grows.

Specifically, how the number of steps changes when we fill the table from the smallest subproblems up.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int fib(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 using bottom-up tabulation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that fills the dp array from 2 to n.
• How many times: Exactly n-1 times (from 2 up to n).

How Execution Grows With Input

Each new input number adds one more step to fill the dp table.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to compute 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: Bottom-up DP solves each subproblem once and stores the result, so it runs in linear time here, not exponential.

Interview Connect

Understanding how bottom-up DP reduces repeated work is a key skill that shows you can write efficient code for problems with overlapping subproblems.

Self-Check

"What if we changed the loop to compute dp[i] using three previous values instead of two? How would the time complexity change?"