import time

# time.perf_counter — wall clock, high precision
start = time.perf_counter()
result = sum(range(1_000_000))
elapsed = time.perf_counter() - start
print(f"{elapsed:.6f}s")

import timeit

# timeit — eliminates startup noise, repeats automatically
t = timeit.timeit(
    "sum(range(1_000_000))",
    number=10
)
print(f"avg: {t/10:.6f}s")

Best / worst / average case

Case	Meaning
Best	Most favourable input
Worst	Most unfavourable input
Average	Expected over all inputs

Big O usually refers to the worst case.

Linear search — O(n)

def linear_search(lst, target):
    for i, item in enumerate(lst):
        if item == target:
            return i
    return -1

Works on any list. Scans every element in the worst case.

Binary search — O(log n)

Requires a sorted list.

def binary_search(lst, target):
    lo, hi = 0, len(lst) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

bisect — maintain sorted order

import bisect

data = [1, 3, 5, 7, 9]

# Find insertion point
i = bisect.bisect_left(data, 6)   # 3

# Insert maintaining sort order
bisect.insort(data, 6)
print(data)   # [1, 3, 5, 6, 7, 9]

# Lookup: is x in the sorted list?
def sorted_contains(lst, x):
    i = bisect.bisect_left(lst, x)
    return i < len(lst) and lst[i] == x

Hash-based — O(1) average

# Preprocess once
lookup = set(data)     # or dict for key→value

# O(1) membership check
print(6 in lookup)     # True

# Summary

Method	Time	Requirement
Linear	O(n)	None
Binary	O(log n)	Sorted
bisect	O(log n)	Sorted
Hash	O(1) avg	Hashable elements

Python's Timsort — O(n log n)

lst = [3, 1, 4, 1, 5, 9, 2, 6]
lst.sort()                        # in-place
s = sorted(lst)                   # new list
s = sorted(lst, reverse=True)     # descending
s = sorted(lst, key=abs)          # custom key

Insertion sort — O(n²) worst

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = key

Merge sort — O(n log n)

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left  = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]