Algorithm Runtime

Insertion sort

Best: Θ(n) (already sorted; inner loop breaks after one comparison). Average: Θ(n^2). Worst: Θ(n^2) (reverse-sorted: n(n-1)/2 comparisons and swaps). Extra space: O(1) (in-place).

Merge sort

Best: Θ(n log n). Average: Θ(n log n). Worst: Θ(n log n) (T(n) = 2T(n/2) + cn). Extra space: O(n) (Merge copies halves into L[] and R[]); not in-place.

Merge step (Merge procedure of merge sort)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (exactly one comparison per element moved). Extra space: O(n) (the L[] and R[] copies).

Heap sort

Best: O(n log n) (Θ(n log n) for distinct keys; linear only if all keys are equal). Average: Θ(n log n). Worst: O(n log n) (BuildHeap O(n) + n Delete-Max calls at O(log n)). Extra space: O(1) (in-place).

Counting sort

Best: Θ(n + k). Average: Θ(n + k). Worst: Θ(n + k) (same for every input; integers in 0..k). Extra space: O(n + k) (count array C[0..k] plus output array of size n). Stable.

Radix sort

Best: Θ(d(n + r)). Average: Θ(d(n + r)). Worst: Θ(d(n + r)) (d counting-sort passes; O(n) if d and r are constants). Extra space: O(n + r) (counting array of size O(r) plus output array of size n). Stable.

Bucket sort

Best: Θ(n) (items spread evenly across buckets). Average: Θ(n) expected (uniformly distributed input, n equal-size buckets). Worst: O(n^2) (all items in one bucket, sorted by insertion sort). Extra space: O(n) (buckets holding the n items).

Find minimum or maximum (linear scan)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (exactly n - 1 comparisons, which is optimal). Extra space: O(1).

Partition step (Randomized-Select / Quicksort style)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (examines each element once against the pivot). Extra space: O(1) if done in place.

Randomized-Select (kth smallest)

Best: Θ(n) (the pivot has rank k; one partition still costs Θ(n)). Average (expected): Θ(n). Worst: Θ(n^2) (always picking the max as pivot: T(n) = T(n-1) + cn). Extra space: O(1) extra besides the recursion stack (about O(log n) expected depth).

Select (median-of-medians, kth smallest in worst-case linear time)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (T(n) = T(n/5) + T(3n/4) + Θ(n)). Extra space: O(n) (array of group medians) plus the recursion stack.

Find max in a max-heap

Best: O(1). Average: O(1). Worst: O(1) (the max is at A[1]). Extra space: O(1).

Bubble-up(A, i)

Best: O(1) (element is not larger than its parent; no swap). Average: O(1) expected for random keys. Worst: O(log n) (swaps all the way to the root). Extra space: O(1).

Insert into a heap

Best: O(1). Average: O(1) expected for random keys. Worst: O(log n) (insert as a leaf, then Bubble-up). Extra space: O(1).

Bubble-down(A, i)

Best: O(1) (no swap needed). Average: O(log n) (for a node near the root of a random heap). Worst: O(log n), more precisely O(h) for a node of height h. Extra space: O(1).

Delete-Max (heap)

Best: O(1) (no swap needed during Bubble-down, e.g., all keys equal). Average: Θ(log n). Worst: O(log n) (swap A[1] with last element, then Bubble-down from the root). Extra space: O(1).

BuildHeap, iterative method (repeated Bubble-up)

Best: O(n) (input already in heap order; no swaps). Average: O(n) for random input. Worst: O(n log n) (each of n insertions bubbles up O(log n)). Extra space: O(1) (in-place).

BottomBuildHeap (bottom-up method with Bubble-down)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (sum of h·n/2^h = 2n). Extra space: O(1) (in-place).

Linear search (unsorted array or list)

Best: O(1) (item is first). Average: O(n). Worst: O(n) (item is last or absent). Extra space: O(1).

Binary search (sorted array)

Best: O(1) (item is at the middle). Average: O(log n). Worst: O(log n). Extra space: O(1) iterative.

Unsorted array: search / insert / delete

Search: best O(1), average O(n), worst O(n). Insert: O(n) (may need to copy to a larger array). Delete: O(n). Space: O(n) for the stored data.

Sorted array: search / insert / delete

Search (binary search): best O(1), average O(log n), worst O(log n). Insert: O(n) (shift elements). Delete: O(n) (shift elements). Space: O(n) for the stored data.

Unsorted linked list: search / insert / delete

Search: best O(1), average O(n), worst O(n). Insert (at the front): O(1). Delete: O(n) (must search first). Space: O(n) for the stored data.

Sorted linked list: search / insert / delete

Search: best O(1), average O(n), worst O(n). Insert: O(n). Delete: O(n). Space: O(n) for the stored data.

Direct-address table (search / insert / delete)

Best: O(1). Average: O(1). Worst: O(1) for all three operations. Space: Θ(m), where m is the size of the key range (can be very wasteful).

Hash table with no collisions (search / insert / delete)

Best: O(1). Average: O(1). Worst: O(1) (go to position h(k)). Space: Θ(m), with m much smaller than the universe.

Hash table with chaining: insert

Best: O(1). Average: O(1). Worst: O(1) (attach to the front or back of the chain at h(k)). Space: O(m + n) (table plus chain nodes).

Hash table with chaining: search / delete

Best: O(1) (key is first in its chain). Average: O(1 + α) under uniform hashing, where α = n/m (O(1) if α is constant). Worst: O(n) (all keys in one chain). Space: O(m + n).

Hash table with open addressing: search / insert / delete

Best: O(1) (first probe succeeds). Average: expected at most 1/(1 - α) probes under uniform hashing (α < 1). Worst: O(n) probes (as the table fills, up to m). Space: O(m), with n ≤ m.

Average-finding algorithm (sum n numbers, divide by n)

Best: Θ(n). Average: Θ(n). Worst: Θ(n) (one pass through the n numbers). Extra space: O(1).