Search code examples
pythonloopstime-complexitybig-omin

Python: Time complexity of min() function inside for loop


I'm calculating time complexities of algorithms and I assumed both code below to have time complexities of O(n^2) However my books says first code is O(n^2) and second one is O(n). I don't understand why. Both are using min/max, so whats the difference? Code 1:

def sum(l, n):

for i in range(1, n - 1):
    x = min(l[0:i])
    y = min(l[i:num])
return x+y

Code 2:

def sum(a, n):
r = [0] * n
l = [0] * n
min_el = a[0]

for i in range(n):
    min_el = min(min_el, a[i])
    l[i] = min_el


print(min_el)

Solution

  • In the first block of code the block of code runs the min function over the whole array, which takes O(n) time. Now considering it is in a loop of length n then the total time is O(n^2)

    Looking at the 2nd block of code. Note that the min function is only comparing 2 values, which is arguably O(1). Now considering that it is in a loop of length n. The total time is simply the summation of O(n+n+n), which is equal to O(n)