Python Tutorial
DSA Time Complexity
Time complexity describes how runtime grows as the input size n grows. We use Big O notation.
Big O Cheatsheet
O(1) constant, O(log n) binary search, O(n) a single loop, O(n log n) merge sort, O(n²) nested loops, O(2ⁿ) naive recursion.
def linear(items):
for x in items: # O(n)
print(x)
def nested(items):
for a in items: # O(n²)
for b in items:
print(a, b)Why It Matters
On 1,000,000 items, O(n) is fine. O(n²) is a trillion operations. Measure the worst case unless you know the data.
n = 1_000_000
print("O(n) ", n)
print("O(n log n)", int(n * 20))
print("O(n²) ", n * n)📘 Real-World Deep Dive
Knowing <strong>DSA Time Complexity (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Time Complexity that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
import timeit
setup = "xs = list(range(10000))"
list_lookup = timeit.timeit("9999 in xs", setup, number=100)
set_lookup = timeit.timeit("9999 in set(xs)", setup, number=100)
print(f"list lookup x100: {list_lookup:.4f}s")
print(f"set lookup x100: {set_lookup:.4f}s")Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Time Complexity as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.