Scribd
Upload
1 views1 page

Python Data Structures Cheatsheet

This study sheet provides a quick reference for Python data structures, their time complexities, and common sorting algorithms. It includes details on built-in data types like lists, dictionaries, sets, and tuples, along with their access, search, and insertion times. Additionally, it covers binary search implementation and useful collections from the collections module.

Uploaded by

f8191572
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
1 views1 page

Python Data Structures Cheatsheet

This study sheet provides a quick reference for Python data structures, their time complexities, and common sorting algorithms. It includes details on built-in data types like lists, dictionaries, sets, and tuples, along with their access, search, and insertion times. Additionally, it covers binary search implementation and useful collections from the collections module.

Uploaded by

f8191572
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

STUDY SHEET #1

Python Data Structures & Time Complexities


A quick-reference study guide for algorithms, Big-O notations, and standard collections.

1. Built-in Data Structures 3. Common Sorting Algorithms

Data Type Access Search Insertion Time


Algorithm Time (Best) Space
(Worst)
List O(1) O(n) O(1) end /
O(n) Quick Sort O(n log n) O(n²) O(log
n)
Dict O(1) O(1) O(1) avg
Merge Sort O(n log n) O(n O(n)
Set N/A O(1) O(1) avg log n)
Tuple O(1) O(n) Immutable Tim Sort O(n) O(n O(n)
log n)

Bubble Sort O(n) O(n²) O(1)


2. Binary Search Implementation

Requires a sorted list. Logarithmic time complexity: O(log


n) . 4. Useful collections Module

def binary_search(arr, target): • deque : Fast double-ended queue with O(1) appends/
low, high = 0, len(arr) - 1 pops from both ends.
while low <= high:
• defaultdict : Dict subclass that calls a factory function
mid = (low + high) // 2
if arr[mid] == target: to supply missing values.
return mid • Counter : Dict subclass for counting hashable objects.
elif arr[mid] < target:
low = mid + 1 from collections import deque, Counter
else:
high = mid - 1 d = deque([1, 2, 3])
return -1 [Link](0) # O(1) time complexity

counts = Counter("hello world")


# Output: Counter({'l': 3, 'o': 2, ...})

Scribd Study Series • Python CS Fundamentals • Page 1 of 1

You might also like