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