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

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.

package main

func fibonacciDP(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for 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.
• How many times: Exactly n-1 times, once for each Fibonacci number from 2 up to n.

How Execution Grows With Input

Each new Fibonacci number requires one addition operation, so the total work grows steadily with n.

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

Pattern observation: The number of operations grows linearly as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the Fibonacci number grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Dynamic programming Fibonacci is still slow because it uses recursion like the naive method."

[OK] Correct: This code uses a loop and stores results, so it does not repeat calculations like naive recursion does.

Interview Connect

Knowing how dynamic programming improves Fibonacci calculation shows you understand efficient problem solving, a key skill in interviews.

Self-Check

"What if we changed the dp array to only store the last two Fibonacci numbers instead of all? 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 avoids repeated calculations by storing intermediate results.

B. It uses less memory by not storing any results.

C. It calculates Fibonacci numbers randomly.

D. It uses recursion without any optimization.

Solution

1. Step 1: Understand recursion inefficiency

   Simple recursion recalculates the same Fibonacci values multiple times, causing exponential time complexity.

2. Step 2: Role of DP in optimization

   DP stores previously computed Fibonacci numbers in a table (memoization or tabulation), avoiding repeated work and improving efficiency.

3. Final Answer:

   It avoids repeated calculations by storing intermediate results. -> Option A

4. Quick Check:

   DP stores results = avoids repeats [OK]

Hint: DP saves past results to speed up Fibonacci calculation [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Believing DP calculates values randomly
• Confusing DP with plain recursion

2. Which of the following Go code snippets correctly initializes a slice to store Fibonacci numbers for DP with size n?

easy

A. fib := new(int)

B. fib := make([]int, n+1)

C. fib := []int{n}

D. fib := [n]int{}

Solution

1. Step 1: Understand slice initialization

   To store Fibonacci numbers up to n, we need a slice of length n+1 to hold indices 0 through n.

2. Step 2: Check each option

   fib := make([]int, n+1) uses make with length n+1, correctly creating a slice. fib := []int{n} creates a slice with one element n, not size n+1. fib := new(int) creates a pointer to int, not a slice. fib := [n]int{} is invalid syntax for slice.

3. Final Answer:

   fib := make([]int, n+1) -> Option B

4. Quick Check:

   make slice with n+1 length = correct [OK]

Hint: Use make([]int, n+1) to create DP slice for Fibonacci [OK]

Common Mistakes:

• Using array syntax instead of slice
• Creating pointer instead of slice
• Initializing slice with wrong length

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

func fibDP(n int) int {
    fib := make([]int, n+1)
    fib[0], fib[1] = 0, 1
    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib[n]
}

fmt.Println(fibDP(5))

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace Fibonacci values in slice

   fib[0]=0, fib[1]=1; then fib[2]=1, fib[3]=2, fib[4]=3, fib[5]=5.

2. Step 2: Return fib[5]

   The function returns fib[5], which is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Trace fib array from 0 to n to find fib[n] [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Returning fib[n-1] instead of fib[n]
• Off-by-one errors in loop

4. Identify the error in this Go function for Fibonacci using DP and select the fix:

func fibDP(n int) int {
    fib := make([]int, n)
    fib[0], fib[1] = 0, 1
    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib[n]
}

medium

A. Return fib[n-1] instead of fib[n].

B. Initialize fib[0] and fib[1] to 1 and 1.

C. Change slice size to n+1 to avoid index out of range.

D. Change loop to for i := 1; i < n; i++.

Solution

1. Step 1: Check slice size and indexing

   Slice fib is created with length n, but loop and return access fib[n], which is out of range.

2. Step 2: Fix slice size

   Increase slice size to n+1 so fib[n] is valid and no runtime error occurs.

3. Final Answer:

   Change slice size to n+1 to avoid index out of range. -> Option C

4. Quick Check:

   Slice size must cover all indices accessed [OK]

Hint: Slice length must be at least n+1 for fib[n] access [OK]

Common Mistakes:

• Not increasing slice size causes runtime panic
• Changing initial values incorrectly
• Modifying loop incorrectly causing wrong results

5. You want to compute the 10th Fibonacci number using DP but with constant space (only two variables). Which Go code snippet correctly implements this optimization?

hard

A. func fib(n int) int {
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}

B. func fib(n int) int {
fib := make([]int, n+1)
fib[0], fib[1] = 0, 1
for i := 2; i <= n; i++ {
fib[i] = fib[i-1] + fib[i-2]
}
return fib[n]
}

C. func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}

D. func fib(n int) int {
a, b := 0, 1
for i := 1; i < n; i++ {
a = b
b = a + b
}
return a
}

Solution

1. Step 1: Understand constant space DP

   We only keep last two Fibonacci numbers and update them iteratively to save space.

2. Step 2: Analyze options

   func fib(n int) int { a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b } correctly updates a and b simultaneously and returns b as fib(n). func fib(n int) int { fib := make([]int, n+1) fib[0], fib[1] = 0, 1 for i := 2; i <= n; i++ { fib[i] = fib[i-1] + fib[i-2] } return fib[n] } uses slice (not constant space). func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) } is simple recursion (inefficient). func fib(n int) int { a, b := 0, 1 for i := 1; i < n; i++ { a = b b = a + b } return a } updates variables incorrectly causing wrong result.

3. Final Answer:

   func fib(n int) int { a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b } -> Option A

4. Quick Check:

   Update two vars simultaneously for constant space [OK]

Hint: Update two vars together to save space in Fibonacci DP [OK]

Common Mistakes:

• Using slice instead of variables for DP
• Incorrect variable update order causing wrong sums
• Using recursion without memoization