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

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, 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.

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):

• 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):

• enqueue(): O(1)
• dequeue(): Amortized O(1) average, O(n) worst-case during stack transfers

Circular Queue (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

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):

• 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):

• 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 and 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)

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 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 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, 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 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):

• 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 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).

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 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 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, 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 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 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, 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 degrades to O(n) when input is sorted or nearly sorted.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}