pythoncomplexity-theoryinfinite-loopnotincode-complexity

Asymptotic complexity in python for O-Upper


I'm studying the complexity of functions in python, and I have this two there Im not sure, one because I think it's infinite loop and second is the not in method build in on python:

1- The function f1 receives a positive integer n and a list v. v is larger than n.

def f1(n, v): 
   b=n*n
   s=0
   while b > 1: 
      s += v[n]
      s += b
      b -= 2 
   return s

2- The function f2 receives a dictionary d and a list l.

def f2(d,l): 
   r = []
   for x in l:
      if x not in d:
         r.append(x)
return r

I am studying them on "O-Upper", O. ex O (n ^ 2) is quadratic. What is the complexity of this two functions?


Solution

  • f1 contains a loop that executes O(n2) times, and it performs only constant-time operations. Like EnderShadow8 explained, this makes your function O(n2).

    f2 contains a loop that executes O(n) times, where n is the length of l. Since d is a Python dictionary, checking if x is in d runs in amortized O(1) time. This is because a dictionary does not in practice iterate through all its elements to find x, but rather it uses an underlying hash map data structure. Appending to a list is also in practice a constant-time operation in Python. Therefore, f2 is actually an O(n) time function.