List Operations/Methods Complexity Python

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)

  1. O(1) means in constant time – independent of the number of items.
  2. O(N) means in proportion to the number of items.
  3. 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.

Operation/MethodExampleComplexity
IndexL[i]O(1)
StoreL[i] = 0O(1)
Lengthlen(L)O(1)
AppendL.append(some value)O(1)
PopL.pop()O(1)
ClearL.clear()O(1)
SliceL[a:b]O(b-a)
ExtendL.extend(some iterable)O(len(some iterable))
Constructionlist(some iterable)O(len(some iterable))
Checks ==, !=List1 == List2O(N)
InsertL[a:b] = …..O(N)
Deletedel L[i]O(N)
Containmentx in/not in LO(N)
CopyL.copy()O(N)
RemoveL.remove(…)O(N)
PopL.pop(value)O(N)
Extreme valuemin(L)/max(L)O(N)
ReverseL.reverse()O(N)
Iterationfor i in L:O(N)
SortL.sort()O(N LogN)
Multiplyk*lO(k N)

You May Also Like

Gagan

Hi, there I'm founder of ComputerScienceHub(Started this to bring useful Computer Science information just at one place). Personally I've been doing JavaScript, Python development since 2015(Been long) - Worked upon couple of Web Development Projects, Did some Data Science stuff using Python. Nowadays primarily I work as Freelance JavaScript Developer(Web Developer) and on side-by-side managing team of Computer Science specialists at ComputerScienceHub.io

Leave a Reply

Your email address will not be published. Required fields are marked *

Recent Posts