Python / Others / Implementation / Operations Complexity

Python Complexity Operations (Big O)

By Marcelo Fernandes Dec 29, 2017

Getting the complexity of your Python code


big o python

Every developer had faced on his lifetime a bunch of messy complex operations to achieve a final functionality on his/hers code that could have been avoided with just a simple thought about code complexity. In fact, even the most experienced developers "commit" this kind of mistake every now and then.

So, let's take a look and try to have a good overview of the subject, you don't need to memorize everything, just having a basic idea of how python handles its operations complexity will save you from a lot of hairy situations on the future.

Let's first take a look at some complexity tables:

List Operations


Name Operation Complexity Observation
Index l[i] O(1)
Store l[i] = 1 O(1)
Length len(l) O(1)
Append l.append(5) O(1)
Pop l.pop(), l.pop(-1) O(1)
Pop l.pop(i) O(N) Searches the list
Clear l.clear() O(1) Same as l = []
Slice l[a:b] O(b-a)
Extend l.extend(l2) O(len(l2))
Building list(...) O(len(...))
Compare ==, != O(N)
Insert l[a:b] O(N)
Delete del l[i] O(N)
Contains x in l O(N) Searches the list
Copy l.copy() O(N)
Remove l.remove(...) O(N)
Extremes max(l), min(l) O(N) Searches the list
Reverse l.reverse() O(N)
Iteration for i in l: O(N)
Sort l.sort() O(N Log N)
Multiply c*l= O(c N)

Set Operations


Name Operation Complexity Observation
Length len(l) O(1)
Add s.add(100) O(1)
Containment x in s O(1)
Remove s.remove(x) O(1)
Discard s.discard(x) O(1)
Pop s.pop(x) O(1)
Clear s.clear() O(1) Same as s = set()
Construction set(...) O(len(...)) Depends on iterable
== or != s != t O(len(s)) False in O(1) if != len
< or <= s <= t O(len(s)) Subset
> or >=/td> s >= t O(len(t)) Superset
Union s | t O(len(s) + len(t))
Intersection s & t O(len(s) + len(t))
Difference s - t O(len(s) + len(t))
Symmetric Diff s ^ t O(len(s) + len(t))
Iteration for x in s O(N)
Copy s.copy(x) O(N)

Dictionary Operations


Name Operation Complexity Observation
Index d[x] O(1)
Store d[x] = y O(1)
Length len(d) O(1)
Delete del d[x] O(1)
Get/Set Default d.method O(1)
Pop d.pop(k) O(1)
Pop Item d.popitem() O(1)
Clear d.clear() O(1)
View d.keys() O(1)
Construction dict(...) O(len(...))
Iteration for i in d: O(N)


Determining the Complexity of a Function

Let's use the information obtained on the tables above to evaluate the complexity of an entire python function, using the combination of what we already know, to calculate nested and sequential statements.


Law of Addition

O( f(n) ) + O( g(n) ) -> is -> O( f(n) + g(n) )


Remember that when we are adding two complexity classes, we drop the one that grows slower, therefore O( f(n) + g(n) ) results will account only the bigger class. Ex:

O( nlog(n) + n ) = O( nlog(n) )

Once nlog(n) is the fastest growing term.


This rule is the one we use when we want to compute the complexity of Sequential Operations. If we have a function f(x) with complexity of O(N) and another function g(x) with complexity of O(1), calling sequentially:

f(x)
g(x)

Will end up on O(N) + O(1) = O(N + 1) = O(N)

Take a look at the next example:



if condition:      # Assume the condition is O(N)
    code_1()       # Assume the code_1 function is O(N^2)
else:
    code_2()       # Assume the code_2 function is O(N log N)


In this case, we gotta look for the worst case scenario. The condition is always evaluated, but the complexity of code_1 is bigger than the complexity of code_2, therefore, for this script we have:

O(N) + max(O(N^2), O(N log N)) = O(N) + O(Nˆ2) = O(Nˆ2)



Law of Multiplication

O( f(n) ) * O( g(n) ) -> is -> O( f(n) * g(n) )


This is quite intuitive once that if we repeat a process O(f(x)) O(N^2) times, we would have O( n^2 ) * O( f(n) ) = O( n^2 * f(n) )

We should take care with this kind of operation, as it could scale to a intense computing calculation:



for i in range(N):
    f(x)            # Suppose f(x) is O(n log n)

In this case we would have: O(n) * O(n log n) = O(n^2 log n)



Examples

Check the following code:


list = [i for i in range(N)]   # Building: O(N)
for i in list:                 # Iteration: O(N)
    if not i % 2:              # Consider % to be O(1)
        return i               # O(1)

# you can also use list comprehensions to achieve that:
l = [i for i in range(N) if not i % 2]


In this example we have:

O(N) + O(N)*(O(1) + O(1)) = O(N) + O(N)*O(1) = O(N) + O(N) = O(N)


Notes


Shortcuts:


Lists
Sets
Dictionaries