Algorithms, Data Structures and Complexity

Introduction

An algorithm is a finite, unambiguous procedure for transforming input into output. A data structure organizes information so that particular operations can be performed efficiently. These ideas are inseparable: selecting a data structure determines which algorithms are practical, while an algorithm’s access patterns determine which data structure is appropriate.

In AI and machine learning systems, such decisions affect data preprocessing, nearest-neighbour retrieval, feature caching, graph traversal, event scheduling and model-serving latency. A correct program may still be unusable if its running time or memory requirements grow too rapidly.

This chapter develops searching, sorting, stacks, queues, linked structures, binary search trees and hash tables in Python. It combines asymptotic analysis with empirical measurement and explicitly distinguishes auxiliary workspace from storage required for returned output.

Learning Objectives

After studying this chapter, students should be able to:

1. Express time and space growth using asymptotic notation.

2. Analyze loops, recursive algorithms and common data-structure operations.

3. Implement and compare linear and binary search.

4. Implement insertion sort and merge sort and explain their properties.

5. Use stacks, queues and linked structures appropriately.

6. Implement and analyze a binary search tree.

7. Implement a hash table using separate chaining for collision handling.

8. Distinguish worst-case, average-case, amortized and expected complexity.

9. Measure Python implementations without confusing empirical timing with mathematical complexity.

10. Select algorithms using workload, correctness, memory and security requirements.

1. A Framework for Algorithm Analysis

Let input size be represented by `n`. Its meaning depends on the problem: the number of records, vertices, characters or matrix entries. Before analyzing an algorithm, both the input-size measure and the basic operation being counted must be defined.

1.1 Time complexity

If `T(n)` denotes the number of relevant elementary operations, asymptotic notation describes its growth for large `n`.

• Big-O: `T(n) = O(g(n))` if constants `c > 0` and `n₀` exist such that `0 ≤ T(n) ≤ c g(n)` for every `n ≥ n₀`. It provides an asymptotic upper bound.
• Big-Omega: `T(n) = Ω(g(n))` if `T(n) ≥ c g(n)` beyond some threshold.
• Big-Theta: `T(n) = Θ(g(n))` when both upper and lower bounds hold; it is a tight asymptotic bound.

For example,

`3n² + 5n + 8 = Θ(n²)`

because the quadratic term dominates as `n` grows. Asymptotic notation suppresses constant factors and lower-order terms, but those factors can remain important in real software.

Frequently encountered growth classes are:

`Θ(1) < Θ(log n) < Θ(n) < Θ(n log n) < Θ(n²) < Θ(2ⁿ)`.

The logarithm base does not change the asymptotic class because logarithms of different fixed bases differ by a constant factor.

1.2 Best, average, expected and worst cases

These terms are not interchangeable:

• Best-case complexity concerns the most favourable valid input of size `n`.
• Worst-case complexity concerns the least favourable valid input.
• Average-case complexity requires a stated probability distribution over inputs.
• Expected complexity may instead average over an algorithm’s random choices, such as randomized pivot selection.
• Amortized complexity averages the cost of a sequence of operations without requiring a probability distribution.

For example, appending to a Python list is normally constant time, but an occasional resize copies existing references. Over a sequence of appends, the amortized time per append is `O(1)`.

1.3 Space complexity and accounting conventions

Space claims must state what is included. This chapter uses three categories:

1. Input storage: memory occupied by supplied input.

2. Output storage: memory intrinsically required to hold returned results.

3. Auxiliary space: temporary workspace beyond input and required output.

A function that returns a new sorted list of `n` references necessarily requires `Θ(n)` output storage. If required output is excluded from auxiliary space, that list must not simultaneously be described as `Θ(n)` auxiliary space. The program’s total additional allocation, however, may still be `Θ(n)` when output storage is included.

An in-place insertion sort below mutates its input and uses `Θ(1)` auxiliary space. A wrapper that first copies the input uses `Θ(n)` returned-output storage and then sorts that output buffer in place; excluding required output, the sorting workspace remains `Θ(1)`.

Recursive call frames count as auxiliary space. A recursion of depth `h` generally requires `O(h)` stack space unless an implementation performs an applicable optimization; standard Python does not optimize tail calls.

2. Reasoning About Iterative and Recursive Algorithms

A single loop performing constant work `n` times has `Θ(n)` time. Nested loops require attention to their bounds. For example:

```python

for i in range(n):

for j in range(i):

process(i, j)

```

The inner operation executes

`0 + 1 + ... + (n - 1) = n(n - 1)/2 = Θ(n²)`

times.

For recursion, a recurrence relates an instance to smaller instances. Merge sort splits a problem into two halves and performs linear merging:

`T(n) = 2T(n/2) + cn`, with `T(1) = d`.

Assuming, for simplicity, that `n = 2ᵏ`, recursion has `log₂ n` splitting levels. The combined merge work at each level is `cn`, so the non-base work is `cn log₂ n`. The `n` base cases add `dn`; therefore `T(n) = Θ(n log n)`.

This derivation applies to balanced halving. It should not be applied automatically to an unbalanced recursion such as poorly pivoted quicksort.

3. Searching

3.1 Linear search

Linear search examines elements in sequence and works on unsorted collections.

```python

def linear_search(values, target):

for index, value in enumerate(values):

if value == target:

return index

return -1

```

Its best-case time is `Θ(1)` and worst-case time is `Θ(n)`. Under a uniform distribution over successful target positions, it performs `(n + 1)/2` comparisons on average. This average statement depends on the stated distribution. The algorithm uses `Θ(1)` auxiliary space.

3.2 Binary search

Binary search requires data sorted according to the same ordering used by the comparisons.

```python

def binary_search(values, target):

low, high = 0, len(values) - 1

while low <= high:

mid = low + (high - low) // 2

if values[mid] == target:

return mid

if values[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

```

Each iteration discards approximately half the remaining interval, yielding `O(log n)` worst-case time and `O(1)` auxiliary space for this iterative implementation. If duplicates exist, this version may return any matching index. Finding the first or last occurrence requires modified boundary logic.

Binary search is not automatically superior. If data must first be sorted for only one query, sorting may cost more than a single linear scan. It is most valuable when data is already ordered or many searches reuse the sorted collection.

4. Sorting

A sorting algorithm may be evaluated by time, space, stability and whether it operates in place.

• A stable sort preserves the relative order of records with equal keys.
• An in-place algorithm uses only a small amount of workspace beyond its input, although definitions sometimes permit `O(log n)` call-stack space.
• An adaptive sort benefits from pre-existing order.

4.1 Insertion sort

Insertion sort grows a sorted prefix by moving larger elements to the right.

```python

def insertion_sort_in_place(values):

for i in range(1, len(values)):

key = values[i]

j = i - 1

while j >= 0 and values[j] > key:

values[j + 1] = values[j]

j -= 1

values[j + 1] = key

return values

def sorted_by_insertion(values):

result = list(values) # returned-output storage: Θ(n)

insertion_sort_in_place(result)

return result

```

The in-place algorithm uses `Θ(1)` auxiliary space. `sorted_by_insertion` allocates `Θ(n)` storage for its required returned list, but adds only `Θ(1)` sorting workspace beyond that output.

On already sorted input, insertion sort performs `Θ(n)` comparisons and no shifts. Reverse-ordered input requires

`1 + 2 + ... + (n - 1) = n(n - 1)/2`

shifts, giving `Θ(n²)` time. Because equal elements are not moved past one another—the condition uses `>` rather than `>=`—the implementation is stable.

4.2 Merge sort

Merge sort recursively sorts two halves and merges them.

```python

def merge_sort(values):

if len(values) <= 1:

return list(values)

mid = len(values) // 2

left = merge_sort(values[:mid])

right = merge_sort(values[mid:])

merged = []

i = j = 0

while i < len(left) and j < len(right):

if left[i] <= right[j]:

merged.append(left[i])

i += 1

else:

merged.append(right[j])

j += 1

merged.extend(left[i:])

merged.extend(right[j:])

return merged

```

Merge sort has `Θ(n log n)` time in best, average and worst cases. For this list-based implementation, peak additional allocated storage is `Θ(n)`, including returned/intermediate lists, and recursion depth is `Θ(log n)`. Its merge rule chooses from the left side on equality, making it stable.

Python’s built-in `sorted` and `list.sort` use Timsort, a stable, adaptive algorithm derived from merge-sort and insertion-sort ideas. Production code should normally use these optimized built-ins rather than handwritten educational sorts.

4.3 Comparison-based lower bound

Any deterministic comparison sort can be represented by a decision tree whose leaves correspond to possible input permutations. Distinguishing `n!` possible orders requires a tree height of at least `ceil(log₂(n!))`, which is `Ω(n log n)`. Thus no general comparison sort can guarantee asymptotically better than `Ω(n log n)` comparisons.

This lower bound does not apply to algorithms that exploit restricted key representations, such as counting sort over a suitably small integer range.

5. Stacks, Queues and Linked Structures

5.1 Stacks

A stack follows last in, first out (LIFO) order. Typical uses include expression evaluation, undo systems, depth-first search and replacing recursion with explicit state.

```python

stack = []

stack.append("task") # push: amortized O(1)

item = stack.pop() # pop from end: O(1)

```

Using `list.pop(0)` for stack or queue removal is inefficient because remaining references must shift, giving `O(n)` time.

5.2 Queues

A queue follows first in, first out (FIFO) order. It supports scheduling, buffering and breadth-first search.

```python

from collections import deque

queue = deque()

queue.append("task") # enqueue: O(1)

item = queue.popleft() # dequeue: O(1)

```

For `deque`, append and removal operations at either end are `O(1)`. Indexed access near the middle is not its intended use.

5.3 Singly linked lists

A linked list stores each value in a node containing a reference to the next node.

```python

class Node:

def __init__(self, value, next_node=None):

self.value = value

self.next = next_node

class LinkedStack:

def __init__(self):

self.head = None

self.size = 0

def push(self, value):

self.head = Node(value, self.head)

self.size += 1

def pop(self):

if self.head is None:

raise IndexError("pop from empty stack")

value = self.head.value

self.head = self.head.next

self.size -= 1

return value

```

Both operations take `O(1)` time. Searching or accessing the item at position `i` requires traversal and is `O(n)` in the worst case. Unlike arrays, linked nodes need not occupy contiguous memory, but each node carries reference overhead and often has poor cache locality. Therefore linked lists are not automatically faster than Python lists.

6. Trees and Binary Search Trees

A tree is a hierarchical structure. In a binary tree, each node has at most two children. A binary search tree (BST) additionally maintains an ordering invariant: keys in a node’s left subtree are smaller, while keys in its right subtree are larger under the chosen duplicate policy.

```python

class BSTNode:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

class BinarySearchTree:

def __init__(self):

self.root = None

def add(self, key):

if self.root is None:

self.root = BSTNode(key)

return

current = self.root

while True:

if key == current.key: # duplicate keys ignored

return

if key < current.key:

if current.left is None:

current.left = BSTNode(key)

return

current = current.left

else:

if current.right is None:

current.right = BSTNode(key)

return

current = current.right

def contains(self, key):

current = self.root

while current is not None:

if key == current.key:

return True

current = current.left if key < current.key else current.right

return False

```

If tree height is `h`, both methods take `O(h)` time. Because these implementations are iterative, they use `O(1)` auxiliary space. A recursive implementation would use `O(h)` call-stack space.

For a balanced BST, `h = Θ(log n)`. Inserting already sorted keys into this unbalanced implementation creates a chain with `h = Θ(n)`. Self-balancing trees such as AVL and red-black trees maintain logarithmic height through rotations. Python’s standard library does not provide a built-in balanced search-tree mapping.

An in-order traversal of a BST produces keys in sorted order. A recursive traversal takes `Θ(n)` time and `O(h)` call-stack space; an iterative traversal can use an explicit stack of the same asymptotic bound.

7. Hash Tables and Collision Handling

A hash table computes a bucket index from a key’s hash value. Because multiple keys can map to the same bucket, every correct hash table requires a collision-resolution policy. Common methods are separate chaining and open addressing.

The following basic implementation uses separate chaining, where each bucket stores a list of key–value pairs:

```python

class ChainedHashTable:

def __init__(self, capacity=8, max_load=0.75):

if capacity < 1:

raise ValueError("capacity must be positive")

self._buckets = [[] for _ in range(capacity)]

self._size = 0

self._max_load = max_load

def _index(self, key):

return hash(key) % len(self._buckets)

def __len__(self):

return self._size

def _resize(self, new_capacity):

old_items = [pair for bucket in self._buckets for pair in bucket]

self._buckets = [[] for _ in range(new_capacity)]

self._size = 0

for key, value in old_items:

self[key] = value

def __setitem__(self, key, value):

index = self._index(key)

bucket = self._buckets[index]

for position, (stored_key, _) in enumerate(bucket):

if stored_key == key:

bucket[position] = (key, value)

return

if (self._size + 1) / len(self._buckets) > self._max_load:

self._resize(2 * len(self._buckets))

index = self._index(key)

bucket = self._buckets[index]

bucket.append((key, value))

self._size += 1

def __getitem__(self, key):

for stored_key, value in self._buckets[self._index(key)]:

if stored_key == key:

return value

raise KeyError(key)

def remove(self, key):

bucket = self._buckets[self._index(key)]

for position, (stored_key, value) in enumerate(bucket):

if stored_key == key:

del bucket[position]

self._size -= 1

return value

raise KeyError(key)

```

The load factor is

`α = number of stored entries / number of buckets`.

Under a simple uniform-hashing assumption and with bounded load factor, search, insertion and deletion have expected `O(1)` time. If many keys collide, a chain can contain `Θ(n)` entries and operations degrade to `O(n)` worst-case time. Resizing costs `Θ(n)` for that operation, but geometric capacity growth supports amortized expected `O(1)` insertion under the stated hashing assumptions.

Keys must have stable hash and equality behaviour while stored. Mutable objects whose hash-relevant state changes would make entries effectively unreachable. Python dictionaries are highly optimized hash tables and should be preferred in production, but the implementation above exposes collision handling explicitly.

8. Comparative Complexity

The following table uses the implementations shown in this chapter. Auxiliary-space entries exclude required returned-output storage unless explicitly stated.

| Operation or algorithm | Time | Auxiliary space | Conditions |

|---|---:|---:|---|

| Linear search | `O(n)` worst case | `O(1)` | No ordering required |

| Iterative binary search | `O(log n)` worst case | `O(1)` | Random access and sorted input |

| In-place insertion sort | `Θ(n²)` worst case | `Θ(1)` | `Θ(n)` best-case time |

| Merge sort shown | `Θ(n log n)` | `Θ(n)` peak additional allocation | Stable; uses list copies |

| Stack push/pop using list end | `O(1)` amortized / `O(1)` | `O(1)` per operation | Occasional list resize |

| Queue enqueue/dequeue using `deque` | `O(1)` | `O(1)` per operation | Operations at ends |

| Linked-stack push/pop | `O(1)` | `O(1)` per operation | Each push allocates a node |

| Iterative BST search | `O(h)` | `O(1)` | `h` is tree height |

| Hash-table lookup | expected `O(1)`, worst `O(n)` | `O(1)` per lookup | Expected bound assumes controlled collisions |

The storage occupied by an entire data structure is separate from per-operation auxiliary space. For example, a linked stack with `n` nodes occupies `Θ(n)` structural storage even though one `push` uses only `O(1)` additional space.

9. Empirical Performance Measurement

Asymptotic analysis predicts growth independently of a particular machine. Benchmarking reveals constants, interpreter overhead, cache effects and implementation quality. Neither replaces the other.

```python

from random import Random

from time import perf_counter

from statistics import median

def benchmark(function, argument_factory, repeats=7):

durations = []

for _ in range(repeats):

argument = argument_factory()

start = perf_counter()

function(argument)

durations.append(perf_counter() - start)

return median(durations)

def experiment(n):

rng = Random(42)

source = [rng.randrange(10 * n) for _ in range(n)]

return benchmark(insertion_sort_in_place, lambda: source.copy())

```

A defensible experiment should:

1. Validate correctness before timing.

2. Test multiple input sizes and distributions.

3. Keep setup outside the timed region unless setup is part of the workload.

4. Use fresh equivalent inputs for mutating algorithms.

5. Repeat measurements and report a robust statistic such as the median.

6. Record Python version, hardware and configuration.

7. Avoid inferring asymptotic complexity from a narrow range of small inputs.

If doubling `n` approximately quadruples time over a sufficiently large and stable range, the observation is consistent with quadratic growth, but it does not prove it. System noise, caching and garbage collection may distort measurements.

10. Applied Case: Indexing AI Inference Events

Background

This is an illustrative case. A machine-learning operations team stores one million inference-event records. Analysts repeatedly retrieve events by unique event identifier and also request chronological reports.

Problem

A list supports efficient append but identifier lookup requires up to one million comparisons. Repeated scans create high latency. Sorting by identifier enables binary search but may conflict with chronological reporting and requires maintenance as new events arrive.

Analysis

For `n = 1,000,000`,

`log₂ n ≈ 19.93`.

Binary search therefore needs on the order of 20 comparisons after sorting. A comparison sort requires on the order of `n log₂ n ≈ 19,931,569` comparison-scale steps, ignoring constants.

Using a worst-case linear-scan estimate, sorting once and then running `q` binary searches becomes comparison-count competitive with `q` complete scans when

`n log₂ n + q log₂ n < qn`.

Solving for `q` gives

`q > n log₂ n / (n - log₂ n) ≈ 19.93`.

Thus roughly 20 or more worst-case searches can justify one reused sort in this simplified model. If successful linear searches average about `n/2` comparisons under uniformly distributed positions, the break-even point is roughly 40 searches. Real constants and update costs must still be measured.

Approach and solution

The team maintains:

• an append-oriented event stream for chronological processing;
• a dictionary-like hash index mapping event IDs to record locations;
• a separate batch-sorted view for range reports;
• a queue for pending inference events;
• bounded retention and archival rules to control memory.

The hash index provides expected constant-time identifier retrieval, while the sorted view supports ordered reporting. The system monitors load factor, lookup latency, collision behaviour and memory usage.

Outcome

The design avoids forcing one structure to serve incompatible access patterns. Point lookup becomes expected `O(1)`, chronological ingestion remains efficient, and sorting is performed only for workloads that benefit from order.

Learning points

1. Data structures should be selected from actual query and update patterns.

2. Maintaining multiple indexes improves speed but increases memory and synchronization obligations.

3. Asymptotic estimates should be checked with production-like measurements.

4. Correctness includes keeping all views consistent after insertion, deletion and retention changes.

11. Engineering, Security and Governance Considerations

Algorithm selection has operational and ethical consequences. Excessive time or memory use can make services unavailable, increase energy consumption and disproportionately harm users with low-powered devices or slow connections.

Hash tables require particular care with untrusted input. Deliberately colliding keys can force worst-case behaviour and create denial-of-service risk. Language runtimes may randomize some hashes, but developers should still apply input limits, monitoring and suitable data structures.

Recursive code should validate depth assumptions because Python raises `RecursionError` for sufficiently deep recursion. Iterative traversal is safer for highly unbalanced or attacker-controlled structures.

Data indexes also duplicate or expose sensitive identifiers. Governance should address access control, retention, deletion propagation and auditability. An index that is not updated after a privacy deletion can retain prohibited references even when the primary record has been removed.

Contemporary systems increasingly use specialized structures: B-trees for storage systems, heaps for priority scheduling, tries for prefix retrieval, Bloom filters for probabilistic membership tests and vector indexes for approximate nearest-neighbour search. These structures trade accuracy, ordering, update cost, storage and concurrency in different ways. Their use does not remove the need for careful complexity analysis.

12. Best-Practice Decision Process

When selecting an algorithm or data structure:

1. Define required operations and their frequencies.

2. Establish correctness invariants, including duplicate and empty-input behaviour.

3. Identify worst-case input size and latency or memory constraints.

4. Compare asymptotic time, space and update costs.

5. Prefer mature built-ins unless custom behaviour is genuinely required.

6. Test adversarial as well as typical inputs.

7. Benchmark reproducibly at realistic scales.

8. Document complexity assumptions, especially probabilistic ones.

9. Monitor production behaviour because workloads evolve.

Chapter Summary

Algorithms specify computational procedures, while data structures shape the cost of executing them. Asymptotic analysis describes growth through upper, lower and tight bounds and must distinguish best, average, expected, amortized and worst cases. Space analysis must also separate input, required output and auxiliary workspace.

Linear search works without ordering but has linear worst-case time. Binary search provides logarithmic search on sorted, randomly accessible data. Insertion sort is simple, stable and adaptive but quadratic in the worst case; merge sort guarantees `Θ(n log n)` time at a linear storage cost in the implementation shown.

Stacks support LIFO processing, queues support FIFO processing, and linked structures provide constant-time endpoint changes while sacrificing random access and cache locality. BST operations depend on tree height; the iterative implementation shown uses constant auxiliary space. Hash tables provide expected constant-time operations under controlled collision behaviour, while separate chaining gives a concrete collision-resolution mechanism.

Complexity analysis should guide design, but empirical experiments are needed to account for constants and computing environments. Professional practice must also address adversarial inputs, privacy, memory consumption, synchronization and maintainability.

Key Terms

Algorithm: A finite and unambiguous procedure for solving a computational problem.

Auxiliary Space: Temporary workspace used beyond input and required output storage.

Asymptotic Analysis: Evaluation of resource growth as input size increases.

Amortized Complexity: Average cost per operation over a sequence without a probability assumption.

Binary Search: A search method that repeatedly halves a sorted search interval.

Binary Search Tree: A binary tree maintaining an ordering relationship among keys.

Collision: The occurrence of different hash-table keys mapping to the same bucket.

Deque: A double-ended queue supporting efficient operations at both ends.

Hash Table: A structure that maps keys to locations using hash values.

Height: The maximum number of edges on a path from a tree node to a descendant leaf.

Invariant: A property that remains true throughout an algorithm or data-structure operation.

Load Factor: The ratio of hash-table entries to buckets.

Queue: A first-in, first-out data structure.

Recurrence: An equation defining cost in terms of smaller problem instances.

Separate Chaining: Collision handling in which each bucket stores multiple entries.

Stability: The property of preserving the relative order of records with equal keys during sorting.

Stack: A last-in, first-out data structure.

Worst-Case Complexity: The maximum resource use over valid inputs of a given size.

Review Questions

Short Answer Questions

1. Distinguish Big-O from Big-Theta notation.

2. Why must binary search receive sorted data?

3. What is the difference between required output storage and auxiliary space?

4. Why can an unbalanced BST have linear search time?

5. What problem does separate chaining solve in a hash table?

Long Answer Questions

1. Compare insertion sort and merge sort in terms of time, stability, memory and suitable workloads.

2. Explain best-case, average-case, expected, amortized and worst-case analysis with examples.

3. Describe the implementation and performance trade-offs among Python lists, deques and linked lists.

4. Explain how BST height affects operations and how self-balancing trees address degeneration.

5. Discuss how load factor, collision handling and resizing affect hash-table performance.

Analytical / Application Questions

1. Design data structures for a hospital triage system requiring FIFO arrival processing, priority escalation and patient-ID lookup. Justify every choice.

2. Implement recursive and iterative BST search, then compare their measured time and auxiliary-space behaviour on balanced and chain-shaped trees.

3. Conduct a reproducible experiment comparing insertion sort, merge sort and Python’s `sorted` on random, sorted and reverse-ordered inputs. Interpret the results using theoretical complexity.

Multiple Choice Questions with Answers

Question 1

Under the chapter's accounting convention, a function copies n input references into the list it returns and then sorts that list in place. What is the correct space description?

A. The returned-output storage is Θ(n), and sorting uses Θ(1) auxiliary space.

B. Both returned-output storage and sorting auxiliary space are Θ(1).

C. Returned-output storage is Θ(1), and sorting auxiliary space is Θ(n).

D. Both returned-output storage and sorting auxiliary space are Θ(n²).

Correct Answer: A. The returned-output storage is Θ(n), and sorting uses Θ(1) auxiliary space.

Question 2

What is the worst-case time complexity of iterative binary search on a sorted random-access sequence?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: B. O(log n)

Question 3

Why is the insertion-sort implementation in the chapter stable?

A. It always selects the smallest remaining element.

B. It uses recursion to preserve positions.

C. It shifts only elements strictly greater than the key.

D. It stores each key in a hash table.

Correct Answer: C. It shifts only elements strictly greater than the key.

Question 4

What are the time and auxiliary-space bounds for the chapter's iterative BST contains method when tree height is h?

A. O(log h) time and O(h) auxiliary space

B. O(h) time and O(1) auxiliary space

C. O(n log n) time and O(n) auxiliary space

D. O(1) time and O(h) auxiliary space

Correct Answer: B. O(h) time and O(1) auxiliary space

Question 5

Which Python structure is most appropriate for O(1) queue removal from the front?

A. A tuple using slicing

B. A set using pop

C. A list using pop(0)

D. A collections.deque using popleft

Correct Answer: D. A collections.deque using popleft

Question 6

A chained hash table stores 600 entries in 800 buckets. What is its load factor?

A. 0.60

B. 0.75

C. 1.25

D. 1.33

Correct Answer: B. 0.75

Question 7

Under controlled load factor and simple uniform hashing, what is the expected lookup time in a chained hash table?

A. O(1)

B. O(log n)

C. O(n log n)

D. O(n²)

Correct Answer: A. O(1)

Question 8

What worst-case condition causes an ordinary unbalanced BST containing n keys to have height Θ(n)?

A. Every node has two children.

B. Keys are distributed evenly across levels.

C. Insertion creates a chain, as can occur with sorted keys.

D. The tree uses iterative search.

Correct Answer: C. Insertion creates a chain, as can occur with sorted keys.

Question 9

For n = 1024 = 2^10, how many balanced splitting levels does merge sort have before reaching size-one subproblems?

A. 8

B. 9

C. 10

D. 1024

Correct Answer: C. 10

Question 10

Which statement correctly describes empirical benchmarking?

A. One timing at a small input size proves asymptotic complexity.

B. Setup must always be included even when it is not part of the workload.

C. Mutating algorithms should repeatedly receive the same already-modified object.

D. Repeated measurements across input sizes complement, but do not replace, asymptotic analysis.

Correct Answer: D. Repeated measurements across input sizes complement, but do not replace, asymptotic analysis.