What is the time-complexity of this for-loop?

Question

for i in range(n - length + 1):
     minimumvalue = min(diskSpace[i:i + length])
     minimumList.insert(len(minimumList), minimumValue)

return(max(minimumArray)

So, for i in range takes O(n) time, python min function is O(n) time and insert is 0(n) time. Since these are inside my for loop would my total time complexity be O(n^2) or O(n)?

Answer 1

It's O(n), because you're wrong about the complexities of the min() and insert() functions.

min() is generally O(n), but you're always calling it with the same length elements. Unless length is dependent on n, this can be treated as constant time.

insert() is also normally O(n), but you're inserting at the end by specifying the position len(minimumList), so this is amortized constant time. In fact, inserting at that position is equivalent to minimumList.append(minimumValue), which is amortized constant time.

The only part of the code that depends on n is the number of iterations of for i in range(n - length + 1):

If length is an input to the complexity, then the total complexity is O(n*length).