Fibonacci Using DP in DSA Java - Time & Space Complexity

Time Complexity: Fibonacci Using DP

O(n)

Understanding Time Complexity

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

Specifically, how the time needed grows as the input number gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int fibonacciDP(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    if (n > 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 building up from smaller results stored in an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each step in the loop does a simple addition and stores the result, so the total work grows directly 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 in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Calculating Fibonacci with DP is as slow as the simple recursive method which repeats calculations many times."

[OK] Correct: The DP method saves previous results and only calculates each Fibonacci number once, so it runs much faster.

Interview Connect

Understanding this time complexity shows you can improve slow recursive solutions by storing results, a key skill in many coding problems.

Self-Check

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

Practice

1. What is the main advantage of using Dynamic Programming (DP) to calculate Fibonacci numbers compared to a simple recursive approach?

easy

A. It uses less memory by not storing any intermediate results.

B. It avoids repeated calculations by storing results of subproblems.

C. It calculates Fibonacci numbers using a closed-form formula.

D. It uses randomization to speed up the calculation.

Solution

1. Step 1: Understand recursive Fibonacci drawbacks

   Simple recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

2. Step 2: How DP improves calculation

   DP stores results of smaller Fibonacci numbers to reuse them, avoiding repeated work.

3. Final Answer:

   It avoids repeated calculations by storing results of subproblems. -> Option B

4. Quick Check:

   DP stores subproblem results = avoids repeats [OK]

Hint: DP saves previous results to avoid repeated work [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Confusing DP with closed-form formulas
• Believing DP uses randomization

2. Which of the following Java code snippets correctly initializes the DP array for Fibonacci calculation of size n?

easy

A. int[] dp = new int[n]; dp[0] = 0; dp[1] = 1;

B. int[] dp = new int[n]; dp[0] = 1; dp[1] = 1;

C. int[] dp = new int[n-1]; dp[0] = 0; dp[1] = 1;

D. int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1;

Solution

1. Step 1: Determine array size for Fibonacci DP

   To store Fibonacci numbers up to n, array size must be n+1 to include index n.

2. Step 2: Check base cases initialization

   Fibonacci starts with dp[0] = 0 and dp[1] = 1, so these must be set correctly.

3. Final Answer:

   int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; -> Option D

4. Quick Check:

   Array size n+1 with dp[0]=0, dp[1]=1 = correct initialization [OK]

Hint: Array size must be n+1 to hold Fibonacci up to n [OK]

Common Mistakes:

• Using array size n instead of n+1
• Initializing dp[0] as 1 instead of 0
• Using array size n-1 causing index errors

3. What is the output of the following Java code snippet?

int n = 5;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Calculate Fibonacci values up to n=5

   dp[0]=0, dp[1]=1 Then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5

2. Step 2: Output dp[5]

   The value at dp[5] is 5, so the output is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) is 5 by definition [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Calculating dp[5] as 8 (Fibonacci(6))
• Off-by-one errors in loop

4. Identify the error in the following Java code for Fibonacci using DP and select the correct fix:

int n = 6;
int[] dp = new int[n];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. Change array size to n+1 to avoid index out of bounds error.

B. Initialize dp[2] = 1 before the loop.

C. Change loop condition to i < n instead of i <= n.

D. Remove dp[0] initialization.

Solution

1. Step 1: Analyze array size and loop bounds

   Array dp has size n (6), but loop runs i from 2 to 6 inclusive, accessing dp[6] which is out of bounds.

2. Step 2: Fix array size to n+1

   Increasing array size to n+1 (7) allows dp[6] access without error.

3. Final Answer:

   Change array size to n+1 to avoid index out of bounds error. -> Option A

4. Quick Check:

   Array size n+1 fixes index error [OK]

Hint: Array size must cover max index used in loop [OK]

Common Mistakes:

• Ignoring index out of bounds exception
• Changing loop condition without fixing array size
• Unnecessary initialization of dp[2]

5. You want to calculate the 10th Fibonacci number using DP but with space optimization to use only two variables instead of an array. Which code snippet correctly implements this?

hard

A. int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c);

B. int a = 0, b = 1; for (int i = 2; i <= 10; i++) { a = a + b; b = a; } System.out.println(b);

C. int a = 0, b = 1; for (int i = 2; i < 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

D. int a = 1, b = 1; for (int i = 2; i <= 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

Solution

1. Step 1: Understand space optimization for Fibonacci

   We only need last two Fibonacci numbers to calculate the next, so two variables plus one temp variable suffice.

2. Step 2: Check loop and initialization correctness

   Start with a=0, b=1 (F0 and F1), loop from 2 to 10 inclusive, update c = a+b, then shift a=b, b=c.

3. Step 3: Verify output

   After loop, c holds Fibonacci(10) = 55, which is printed.

4. Final Answer:

   int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c); -> Option A

5. Quick Check:

   Two vars + temp, correct loop = Fibonacci(10) [OK]

Hint: Use two vars and update in loop to save space [OK]

Common Mistakes:

• Incorrect loop bounds causing off-by-one
• Wrong initial values for a and b
• Not updating variables in correct order