# Average and Worst-Case Time Complexity for Data Structures in TheAlgorithms/Python

> Explore average and worst-case time complexity for Python data structures in TheAlgorithms/Python. Understand operation performance from O(1) to O(n).

- Repository: [The Algorithms/Python](https://github.com/TheAlgorithms/Python)
- Tags: deep-dive
- Published: 2026-02-24

---

**The average and worst-case time complexity for operations in TheAlgorithms/Python ranges from O(1) amortized for Disjoint Sets to O(n) worst-case for degenerate Binary Search Trees, with most core structures providing O(1) or O(log n) guarantees.**

Understanding the performance characteristics of data structures is essential for writing efficient algorithms. TheAlgorithms/Python repository implements classic data structures with documented time complexities that directly reflect their underlying algorithmic behavior. This analysis examines the average-case and worst-case complexities for operations across stacks, queues, heaps, trees, and hashing implementations as found in the source code.

## Linear Structures: Stacks and Queues

The repository provides multiple queue implementations with distinct complexity trade-offs, alongside a standard stack implementation.

### Stack Operations (O(1) Guaranteed)

In [`data_structures/stacks/stack.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/stacks/stack.py), the `Stack` class uses Python lists to provide constant-time operations. The `push()` method relies on list `append()`, while `pop()` uses the built-in `pop()` method.

```python
from data_structures.stacks.stack import Stack

s = Stack()
s.push(10)      # O(1) average and worst-case

s.push(20)      # O(1)

top = s.peek()  # O(1)

s.pop()         # O(1)

```

All stack operations maintain **O(1)** complexity in both average and worst-case scenarios because Python list appends and pops from the end operate in constant time.

### Queue Implementations: Three Approaches

The repository contains three distinct queue implementations with different performance characteristics:

**List-Backed Queue** ([`data_structures/queues/queue_by_list.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/queue_by_list.py)):
- `enqueue()`: **O(1)** average and worst-case (list append)
- `dequeue()`: **O(1)** average but **O(n)** worst-case (pop index 0 requires element shifting)

**Two-Stack Queue** ([`data_structures/queues/queue_by_two_stacks.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/queue_by_two_stacks.py)):
- `enqueue()`: **O(1)**
- `dequeue()`: **Amortized O(1)** average, **O(n)** worst-case during stack transfers

**Circular Queue** ([`data_structures/queues/circular_queue.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/circular_queue.py)):
- `enqueue()` and `dequeue()`: **O(1)** guaranteed for both average and worst-case using array indexing with wrap-around logic

```python
from data_structures.queues.circular_queue import CircularQueue

cq = CircularQueue(10)
cq.enqueue(5)   # O(1)

cq.enqueue(10)  # O(1)

val = cq.dequeue()  # O(1) - no element shifting required

```

## Linked Lists: Singly vs. Doubly Linked

The linked list implementations demonstrate how pointer structure affects operation complexity.

**Singly Linked List** ([`data_structures/linked_list/singly_linked_list.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/linked_list/singly_linked_list.py)):
- Insert at head: **O(1)**
- Insert at tail: **O(n)** (requires full traversal)
- Search: **O(n)** average and worst-case

**Doubly Linked List** ([`data_structures/linked_list/doubly_linked_list.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/linked_list/doubly_linked_list.py)):
- Delete given node: **O(1)** (with direct reference), compared to **O(n)** for singly linked lists

The doubly linked implementation maintains previous pointers, enabling constant-time deletion without traversal once the node is located.

## Heap Variants and Priority Queues

The heap implementations provide logarithmic guarantees for dynamic ordering operations.

### Binary Heaps (Min and Max)

Both [`data_structures/heap/min_heap.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/heap/min_heap.py) and [`data_structures/heap/max_heap.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/heap/max_heap.py) implement binary heaps with identical complexity profiles:

- `insert()`: **O(log n)** (sift-up operation)
- `extract_min()` / `extract_max()`: **O(log n)** (sift-down operation)
- `decrease_key()`: **O(log n)**

```python
from data_structures.heap.min_heap import MinHeap

heap = MinHeap()
heap.insert(5)   # O(log n)

heap.insert(3)   # O(log n)

minimum = heap.extract_min()  # O(log n) - returns 3

```

### Binomial Heap

The [`data_structures/heap/binomial_heap.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/heap/binomial_heap.py) implementation offers **O(log n)** amortized complexity for `insert()`, `merge()`, and `delete_min()` operations. While individual operations may occasionally require **O(log n)** time, the amortized analysis ensures logarithmic bounds across sequences of operations.

### List-Based Priority Queue

The [`data_structures/queues/priority_queue_using_list.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/priority_queue_using_list.py) provides a naive implementation:
- `push()`: **O(1)** (simple append)
- `pop_max()` / `pop_min()`: **O(n)** (linear scan to find extremum)

## Tree-Based Structures

The repository includes several specialized tree structures with complexity characteristics tied to their specific use cases.

### Trie (Prefix Tree)

In [`data_structures/trie/trie.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/trie/trie.py), operations scale with key length rather than dataset size:
- `insert(word)`: **O(m)** where *m* is word length
- `find(word)`: **O(m)**
- `delete(word)`: **O(m)**

This makes tries optimal for prefix searching across large dictionaries where query length remains constant relative to the number of stored words.

### Suffix Tree

The [`data_structures/suffix_tree/suffix_tree.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/suffix_tree/suffix_tree.py) implements Ukkonen's algorithm:
- Construction: **O(n)** linear time where *n* is text length
- Pattern search: **O(m)** where *m* is pattern length

### Binary Search Tree and Treap

**Standard BST** implementations (found in `data_structures/binary_tree/` modules):
- `insert()`, `search()`, `delete()`: **O(log n)** average (balanced trees), **O(n)** worst-case (degenerate/skewed trees)

**Treap** ([`data_structures/binary_tree/treap.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/binary_tree/treap.py)):
- `insert()`, `erase()`, `search()`: **O(log n)** expected time (randomized priorities provide probabilistic balance)
- Worst-case remains **O(n)** but occurs with exponentially low probability

## Disjoint Set (Union-Find)

The [`data_structures/disjoint_set/disjoint_set.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/disjoint_set/disjoint_set.py) implements the union-find data structure with path compression and union by rank:

- `make_set()`, `find()`, `union()`: **α(n)** amortized (inverse Ackermann function)

The inverse Ackermann function α(n) grows so slowly that it is effectively **O(1)** for all practical purposes (α(n) ≤ 5 for any realistic *n*).

```python
from data_structures.disjoint_set.disjoint_set import DisjointSet

ds = DisjointSet()
ds.make_set(1)
ds.make_set(2)
ds.union(1, 2)  # O(α(n)) - effectively constant

root = ds.find(1)  # O(α(n)) with path compression

```

## Hashing and Probabilistic Structures

### Hash Table with Open Addressing

The [`data_structures/hashing/hash_map.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/hashing/hash_map.py) uses open addressing with linear probing:

- `insert()`, `search()`, `delete()`: **O(1)** average-case (assuming low load factor and good hash distribution)
- **O(n)** worst-case (hash collisions creating clusters or when resizing is required)

### Bloom Filter

The probabilistic membership structure in [`data_structures/hashing/bloom_filter.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/hashing/bloom_filter.py) provides:
- `add()`, `query()`: **O(k)** where *k* is the number of hash functions (constant time independent of dataset size)

Bloom filters trade absolute accuracy for space efficiency, offering constant-time operations with a controllable false-positive rate.

## Summary

- **Constant Time O(1)**: Stack operations, circular queue enqueue/dequeue, and disjoint set operations (effectively) provide guaranteed or amortized constant time.
- **Logarithmic O(log n)**: Binary heaps, binomial heaps, and treaps offer logarithmic bounds for ordered operations, with treaps providing expected rather than guaranteed bounds.
- **Linear O(n)**: Singly linked list tail insertion, list-backed queue dequeue (worst-case), and degenerate BST operations require linear traversal.
- **Length-Based O(m)**: Trie and suffix tree operations depend on key or pattern length, independent of total stored elements.
- **Probabilistic O(k)**: Bloom filters operate in constant time relative to the number of hash functions, not dataset size.

## Frequently Asked Questions

### What causes the O(n) worst-case complexity in the list-backed queue?

In [`data_structures/queues/queue_by_list.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/queue_by_list.py), the `dequeue()` operation uses `pop(0)` on the internal Python list. While this appears constant-time, removing the first element requires shifting all remaining elements down by one index position. When the queue contains *n* elements, this shifting operation requires **O(n)** time in the worst case.

### How does the circular queue achieve O(1) dequeue operations?

The [`data_structures/queues/circular_queue.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/queues/circular_queue.py) implementation maintains head and tail pointers that wrap around a fixed-size array using modulo arithmetic. Instead of removing elements from the front (which requires shifting), it simply advances the head pointer index. This array indexing operation executes in constant time regardless of queue size, providing **O(1)** dequeue complexity.

### Why is the disjoint set considered "effectively O(1)" rather than strictly O(1)?

The [`data_structures/disjoint_set/disjoint_set.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/disjoint_set/disjoint_set.py) implements path compression and union by rank, resulting in **α(n)** amortized complexity, where α is the inverse Ackermann function. This function grows so slowly that for any practical number of elements (up to 2^65536), α(n) is less than 5. While mathematically not constant, it is effectively bounded by a small constant for all real-world applications.

### When should I choose a Treap over a standard binary search tree?

According to [`data_structures/binary_tree/treap.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/binary_tree/treap.py), you should select a Treap when you need **O(log n)** expected performance guarantees without implementing explicit balancing logic (like AVL or Red-Black trees). The randomized priority assignments in Treaps maintain balance probabilistically, offering average-case **O(log n)** for insertions, deletions, and searches, whereas a standard BST in [`data_structures/binary_tree/binary_tree_node_sum.py`](https://github.com/TheAlgorithms/Python/blob/main/data_structures/binary_tree/binary_tree_node_sum.py) degrades to **O(n)** when input is sorted or nearly sorted.