List Python Data Structures are collections of objects and are mutable, have no fixed size. As Lists are mutable meaning these can be changed? Then how this can be done. There are many Methods/Operations for Updating Lists. I’ve put together an article listing and explaining all of List Methods in Python, you can check that article here – List Methods in Python.
In this article let’s talk about Complexity of list Methods in Python? But let’s first talk about What’s Complexity in programming and why you as a Develop need to care about?
What is Complexity in Programming?
Complexity or O(n) is measurement of How many items needed to be considered for execute something. From daily life you can think this of as brushing your teeth, How many steps items you need to do brushing can be consider Complexity.(Quite Simple!!)
Why Programmer need to consider Complexity? Complexity needs to be considered by programmer while writing code as sometimes a piece of code need to be executed fast or sometime slower. For example – If your writing code for a Self Driving Car then you want code to be executed faster so that action(Turning Left/Right) can be taken quickly.
Defining Complexity Mathematically O(n)
- O(1) means in constant time – independent of the number of items.
- O(N) means in proportion to the number of items.
- O(log N) means a time proportional to log(N)
Basically any ‘O’ notation means an operation will take time up to a maximum of k*f(N)
where: k is a constant multiplier and f() is a function that depends on N
Table containing List Operations/Methods Complexity
Just keep in mind that L in below table is a Python List.
|Store||L[i] = 0||O(1)|
|Extend||L.extend(some iterable)||O(len(some iterable))|
|Construction||list(some iterable)||O(len(some iterable))|
|Checks ==, !=||List1 == List2||O(N)|
|Insert||L[a:b] = …..||O(N)|
|Containment||x in/not in L||O(N)|
|Iteration||for i in L:||O(N)|