Python Dictionary Time Complexity

Python Dictionary is an unordered collection of key:value pairs. As Dictionaries are mutable meaning key, value pair can be added or removed from these. For doing this, Python have a number of Methods/Operations. I’ve put together an article explaining all of Dictionary Methods you can see that article here – Dictionary Methods/Operations in Python.
Let’s first try to understand What’s meaning of Complexity in Programming and Why you as a Python Developer need to care about this while writing code.

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 Dictionary Operations/Methods Complexity

Just keep in mind that d is a dicitonary, i is some key and v is some value in below table.

Operation/MethodExampleComplexity
Indexd[i]O(1)
Stored[i] = vO(1)
Lengthlen(d)O(1)
Deletedel d[i]O(1)
get/setdefaultd.get[i]O(1)
Popd.pop(v)O(1)
Pop itemd.popitem()O(1)
Cleard.clear()O(1)
Viewd.keys()O(1)
Constructiondict(….)O(len(……))
Iterationfor i in d:O(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