By Marcelo Fernandes Dec 29, 2017
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:
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) |
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) |
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) |
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.
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)
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)
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)