1

I need to confirm if my approach to finding the time and space complexity for the below algorithm is correct:

I have an input list and we can take the following as an example : [1,100,1,1,1,100,1,1,100,1] and let us call the given list as cost. I am modifying the given list as per my algorithm below

My algorithm:

  1. Loop through the list (starting from position 2) till the end of the input list.
  2. We perform the following operation: cost[i] = cost[i] + min(cost[i-1],cost[i-2])
  3. We eventually check for the last 2 elements and take the minimum value from the last two elements = min = min(last element,second last element).

My approach to calculate the time complexity : 1. For step 1 = O(n) 2. For step 2 = O(1) + O(n) (to calculate the minimum among the two elements) 3. For step 3 = O(1)

Hence Time complexity = O(n) + O(1) + O(n) + O(1) = O(n) . Space complexity = O(n) [ Simple assumption that the space required will be to store the list]. Can someone please let me know if my approach to calculate the complexities is valid?

Regards, Anubhav

Ekesh Kumar
  • 476
  • 4
  • 12
Anubhav Pareek
  • 13
  • 3

1 Answers1

0

This is a pretty straightforward dynamic programming algorithm.

Your final answers are correct if you're using a list. However, you can actually improve the space complexity to O(1) by using the fact that your dynamic programming recurrence is "memoryless" in the sense that we only need the previous two values to compute the next value. Thus, rather than storing the entire list, you can just store two "previous" values. This idea is similar to the idea behind computing Fibonacci numbers in O(1) space and O(n) time.

Ekesh Kumar
  • 476
  • 4
  • 12