Scribd
Upload
7 views2 pages

Python Data Structures Time Complexity Guide

The document outlines the time complexity of various operations for Python data structures including lists, dictionaries, sets, and tuples. It provides average and worst-case scenarios for operations such as accessing elements, inserting, removing, and searching. This information is crucial for understanding the performance implications of using these data structures in Python.

Uploaded by

perumallapallisundeep
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Python Data Structures Time Complexity Guide

The document outlines the time complexity of various operations for Python data structures including lists, dictionaries, sets, and tuples. It provides average and worst-case scenarios for operations such as accessing elements, inserting, removing, and searching. This information is crucial for understanding the performance implications of using these data structures in Python.

Uploaded by

perumallapallisundeep
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Python Data Structures Time Complexity

List

Operation Average Case Worst Case Description

lst[i] O(1) O(1) Direct access by index

[Link](x) O(1)* O(n) Amortized O(1); O(n) if resizing

[Link](i, x) O(n) O(n) Shifts elements to the right

[Link]() O(1) O(1) Removes last item

[Link](i) O(n) O(n) Removes item at index and shifts others

[Link](x) O(n) O(n) Searches and removes first occurrence

x in lst O(n) O(n) Linear search

for x in lst O(n) O(n) Linear traversal

Dictionary

Operation Average Case Worst Case Description

d[k] (get value) O(1) O(n) Direct access via key (hash lookup)

d[k] = v (insert) O(1) O(n) Insert or update key-value pair

del d[k] O(1) O(n) Remove key-value pair

k in d (check key) O(1) O(n) Check if key exists

for k in d O(n) O(n) Iterates over all keys

Set

Operation Average Case Worst Case Description

x in s (search) O(1) O(n) Hash-based membership check

[Link](x) O(1) O(n) Adds element if not present

[Link](x) O(1) O(n) Removes item; error if not found

[Link](x) O(1) O(n) Removes item if present (no error)

for x in s O(n) O(n) Iterates over all elements


Tuple

Operation Average Case Description

t[i] (indexing) O(1) Access element by index

x in t (search) O(n) Linear scan (no hashing)

for x in t O(n) Sequential traversal

You might also like