CODEWITHSUNDEEP
pythonlistfor-looptimecomplexity-theory
I J
I J

Reputation: 23

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

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)?

Upvotes: 0

Views: 1111

Answers (2)

Barmar
Barmar

Reputation: 781058

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).

Upvotes: 2

S3gfault
S3gfault

Reputation: 393

The min function is O(n), because it is a constant amount of operations per element ( n * some constant). Your for loop does a this for each element (n * (some constant * n)).

So that would be n * n (We can leave out the constant, because that is not really important to see how well this function scales), thus your runtime is O(n^2).

Upvotes: 0

Related Questions