Which of the following are true of a hash table that resolves collisions by chaining?

With a good hash function and a reasonable load factor, average-case search is O(1)

Increasing the load factor beyond a point increases the average chain length at each slot

With a good hash function and a reasonable load factor, average-case search is O(1)

Worst-case search is always O(1), regardless of how many keys collide

Increasing the load factor beyond a point increases the average chain length at each slot

Two distinct keys can never hash to the same index if the table is large enough

Quicksort degrades to its Θ(n²) worst case on an already-sorted array when the pivot is chosen as

the first element, every single time

a randomly chosen element each time

the median of three sampled elements

the first element, every single time

a different random position at each recursive call

Starting from a source vertex in an unweighted graph, which traversal is guaranteed to find the shortest path (fewest edges) to every reachable vertex?

Neither, without edge weights recorded

Dijkstra's algorithm can give an incorrect shortest-path result on a graph that contains

more than one edge between the same pair of vertices

On a graph stored as an adjacency list, Dijkstra's algorithm implemented with a binary-heap priority queue runs in

O(V log V) alone, ignoring the edges entirely

Programming, Data Structures and Algorithms

Section 4 of the GATE Data Science and Artificial Intelligence (DA) paper. Every model a data scientist trains sits on top of code that has to run correctly and finish in time, and this section examines that foundation directly: programming in Python, the handful of data structures — stacks, queues, linked lists, trees, hash tables — that every larger structure in this paper is built from, the search and sorting algorithms that are the first place efficiency is actually reasoned about rather than assumed, the divide-and-conquer technique that mergesort and quicksort both apply, and graph theory with the traversal and shortest-path algorithms that turn a network of relationships into something a computer can search.

1. Python, and the first data structures: stacks and queues

The syllabus names Python specifically, because a data-science programme cares less about a language's full feature set than about the structures its standard library and ecosystem hand you ready-made. A stack is Last-In-First-Out (LIFO): push adds to the top, pop removes from the top, and both are O(1). A queue is First-In-First-Out (FIFO): enqueue adds at the rear, dequeue removes from the front, and both should be O(1) too — provided the underlying structure actually supports removal from the front cheaply.

⚠️ Python's list.pop(0) is not O(1)

A Python list is a dynamic array, and removing its first element means shifting every remaining element one position left — O(n), not O(1). Using a plain list as a queue via pop(0) quietly turns an O(1)-per-operation structure into an O(n)-per-operation one; the standard library's own deque (double-ended queue) is built for O(1) append and pop at both ends, which is the structure this section's queue actually describes.

A stack's classic use is undoing recursion by hand — every function call frame is itself pushed onto a call stack, which is why deep unbounded recursion overflows it.
A queue's classic use is breadth-first traversal, where 'process everything at this level before the next' is exactly what a FIFO order gives for free.

2. Linked lists, trees and hash tables

A linked list stores each element in its own node carrying a pointer to the next, so insertion or deletion at a known position is O(1) once you are there — no shifting — but reaching that position, or any position by index, costs O(n) because there is no random access, unlike an array's O(1) indexing. A tree generalises a linked list by letting a node have more than one 'next': a binary tree has at most two children per node, and its shape decides whether an operation on it is O(log n) (a balanced tree) or degrades to O(n) (a tree that has become a straight chain).

A hash table maps a key to an array index via a hash function, giving average-case O(1) insertion, lookup and deletion — the closest thing on this list to 'free' random access by an arbitrary key rather than by a numeric position. Two keys hashing to the same index is a collision, resolved either by chaining (each slot holds a small list of the keys that landed there) or open addressing (probe forward to the next free slot); either way, worst-case lookup is O(n) when collisions pile up, which is why a good hash function and a load factor kept in check matter more than the resolution scheme chosen.

Typical time complexity by structure (average case)
Structure	Access by index/key	Search	Insert
Array	O(1)	O(n)	O(n)
Linked list	O(n)	O(n)	O(1) at known node
Balanced binary tree	O(log n)	O(log n)	O(log n)
Hash table	O(1) average	O(1) average	O(1) average

3. Search algorithms and basic sorting

Linear search checks every element in turn, O(n), and needs nothing assumed about the data. Binary search repeatedly halves the search range by comparing the target to the middle element, O(log n) — but only on data that is already sorted; run it on unsorted data and it can return the wrong answer or miss an element that is genuinely present, because the halving step's whole logic depends on order.

Selection sort repeatedly finds the minimum of the unsorted remainder and swaps it into place — always exactly n(n-1)/2 comparisons, regardless of the input's starting order, so its best and worst case are the same. Bubble sort repeatedly swaps adjacent out-of-order pairs, and an implementation that stops early when a whole pass makes no swap reaches O(n) on an already-sorted array. Insertion sort builds a sorted prefix one element at a time, inserting each new element into its correct place among those already sorted: O(n²) worst case, but O(n) best case on nearly-sorted data, because each new element then needs almost no shifting at all.

🎯 Why insertion sort still beats 'better' sorts in practice

An O(n log n) sort is asymptotically faster than an O(n²) one only once n is large enough for the constants and lower-order terms to stop mattering. On small arrays, or on data that is already nearly sorted (a common case in practice, e.g. merging a small batch of new records into an already-sorted collection), insertion sort's near-linear best case and low constant overhead genuinely win, which is why production sort implementations often fall back to it below a small size threshold inside a larger, asymptotically faster sort.

4. Divide and conquer: mergesort and quicksort

Both algorithms split the array, recurse on the parts, and combine — the divide-and-conquer pattern named in the syllabus — but they split the work differently. Mergesort splits the array in half by position, sorts each half recursively, then merges the two sorted halves in O(n): the split is trivial and the combine step does the real work. Its running time is Θ(n log n) in every case — best, worst and average alike — because the split is always even regardless of the data, but it needs O(n) auxiliary space for the merge step and is stable (equal elements keep their relative order).

Quicksort splits by value instead of position: it picks a pivot, partitions the array so everything smaller sits to its left and everything larger to its right (the real work), then recurses on the two sides, which are already correctly placed relative to the pivot and need no combining step at all. In-place and cache-friendly in practice, it averages Θ(n log n) — but its worst case is Θ(n²), reached whenever the partition is maximally unbalanced at every step.

⚠️ Quicksort's worst case is not a rare edge case if you pick the pivot naively

Always choosing the first (or last) element as the pivot makes an already-sorted or reverse-sorted array — an entirely ordinary input, not a contrived adversarial one — hit the Θ(n²) worst case every time, because every partition puts all n-1 remaining elements on one side. This is why real implementations randomise the pivot or use median-of-three: doing so does not remove the worst case in theory, but it removes the ordinary, likely-to-occur inputs that used to trigger it.

5. Graph theory basics and graph algorithms: traversal and shortest paths

A graph is a set of vertices and edges connecting pairs of them, stored either as an adjacency matrix (O(V²) space, O(1) edge lookup) or an adjacency list (O(V+E) space, better when the graph is sparse — the usual case). Breadth-first search (BFS) explores level by level using a FIFO queue, visiting every vertex at distance k before any vertex at distance k+1; depth-first search (DFS) explores as far as possible along one branch before backtracking, using a stack (explicit or via recursion), and is the natural tool for connectivity and cycle detection rather than for distance.

ℹ️ BFS gives the shortest path for free; DFS does not

Because BFS visits vertices strictly in order of increasing distance (number of edges) from the source, the first time it reaches any vertex is via a shortest path to it — this holds only for unweighted graphs, where every edge counts as one step. DFS gives no such guarantee at all: it can reach a vertex via a long, winding path while a much shorter one exists elsewhere in the graph, simply because it happened to go deep first.

Dijkstra's algorithm extends this idea to weighted graphs: it repeatedly picks the not-yet-finalised vertex with the smallest known distance from the source (using a priority queue), finalises it, and relaxes (updates) the distance to each of its neighbours. It finds the correct shortest path from the source to every other vertex, provided every edge weight is non-negative — the greedy 'finalise the closest known vertex' step is only safe when no later edge can make an already-finalised vertex's distance decrease, which a negative edge weight can violate.

Key takeaways

Stacks are LIFO with O(1) push/pop; queues are FIFO — but a Python list used as a queue via pop(0) is O(n) per call, not O(1), because a list shifts elements to remove from the front.
A linked list trades O(1) insertion/deletion at a known node for O(n) access by position; a hash table gives average-case O(1) access by key but its worst case degrades to O(n) as collisions pile up.
Binary search needs sorted data and runs in O(log n); insertion sort is O(n²) worst case but O(n) on nearly-sorted input, which is why it still beats asymptotically faster sorts on small or almost-sorted arrays.
Mergesort is always Θ(n log n) but needs O(n) extra space; quicksort is in-place and averages Θ(n log n) but degrades to Θ(n²) on an already-sorted array unless the pivot is chosen randomly or by median-of-three.
BFS visits vertices in order of distance and finds shortest paths in unweighted graphs; Dijkstra's algorithm generalises this to non-negative edge weights, and its greedy step is unsafe the moment a negative edge weight is allowed.

Practice questions (13)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

In Python, repeatedly calling list.pop(0) to implement a queue has which per-call time complexity?
1. O(1)
2. O(log n)
3. O(n)
4. O(n²)
Show answer
Answer: C — O(n)
Removing the first element of a Python list requires shifting every remaining element one position left, which is O(n); a deque is the structure built for O(1) removal from the front.
Which data structure naturally implements the LIFO order that underlies function-call recursion?
1. Queue
2. Stack
3. Hash table
4. Binary search tree
Show answer
Answer: B — Stack
Each recursive call's frame is pushed onto a call stack and popped when that call returns, which is exactly LIFO order.
Which of the following are true of a hash table that resolves collisions by chaining?
1. With a good hash function and a reasonable load factor, average-case search is O(1)
2. Worst-case search is always O(1), regardless of how many keys collide
3. Increasing the load factor beyond a point increases the average chain length at each slot
4. Two distinct keys can never hash to the same index if the table is large enough
Show answer
Answer: A — With a good hash function and a reasonable load factor, average-case search is O(1); C — Increasing the load factor beyond a point increases the average chain length at each slot
Average-case O(1) is the whole point of a hash table, but worst case degrades to O(n) when many keys collide into one chain; a larger table lowers collision probability but never eliminates it, since the pigeonhole principle still applies once keys outnumber available slots.
Binary search on an array requires that the array first be
1. sorted
2. stored as a linked list
3. of even length
4. hashed into a hash table
Show answer
Answer: A — sorted
Binary search decides which half to discard by comparing the target with the middle element; that comparison only tells you anything useful when the array is already sorted.
Insertion sort's best-case time complexity, achieved on an already-sorted array, is
1. O(n)
2. O(n log n)
3. O(n²)
4. O(log n)
Show answer
Answer: A — O(n)
On an already-sorted array, each new element only needs one comparison against the element just before it and no shifting at all, giving O(n) overall.
In its standard implementation, selection sort makes the same number of comparisons regardless of the input's order. How many comparisons does it make on an array of n = 5 elements?
Numerical answer — type the value.
Show answer
Answer: 10
Selection sort always makes n(n-1)/2 comparisons to find each pass's minimum, regardless of the starting order; for n = 5 that is 5×4/2 = 10.
Which sorting algorithm runs in Θ(n log n) time in the worst case as well as the average case, at the cost of O(n) additional space?
1. Quicksort
2. Mergesort
3. Insertion sort
4. Selection sort
Show answer
Answer: B — Mergesort
Mergesort always splits the array evenly regardless of the data, so its worst and average case are both Θ(n log n); the merge step needs O(n) auxiliary space.
Quicksort degrades to its Θ(n²) worst case on an already-sorted array when the pivot is chosen as
1. a randomly chosen element each time
2. the median of three sampled elements
3. the first element, every single time
4. a different random position at each recursive call
Show answer
Answer: C — the first element, every single time
Always taking the first element on an already-sorted array makes it the smallest present, so every partition puts all n-1 remaining elements on one side, giving the maximally unbalanced split at every step.
Starting from a source vertex in an unweighted graph, which traversal is guaranteed to find the shortest path (fewest edges) to every reachable vertex?
1. Depth-first search (DFS)
2. Breadth-first search (BFS)
3. Both equally
4. Neither, without edge weights recorded
Show answer
Answer: B — Breadth-first search (BFS)
BFS visits vertices strictly in order of increasing distance from the source, so the first time it reaches any vertex is necessarily via a shortest path, in an unweighted graph.
Dijkstra's algorithm can give an incorrect shortest-path result on a graph that contains
1. a cycle
2. an edge of weight zero
3. a negative-weight edge
4. more than one edge between the same pair of vertices
Show answer
Answer: C — a negative-weight edge
Dijkstra's greedy step finalises the closest known vertex and never revisits it; a later negative-weight edge could otherwise have shortened the path to it, which the algorithm has no way to discover once that vertex is finalised.
On a graph stored as an adjacency list, Dijkstra's algorithm implemented with a binary-heap priority queue runs in
1. O(V²)
2. O(V + E)
3. O((V + E) log V)
4. O(V log V) alone, ignoring the edges entirely
Show answer
Answer: C — O((V + E) log V)
Each of the E edges can trigger a decrease-key/insert operation costing O(log V) on a binary heap, and each of the V vertices is extracted once at O(log V), giving O((V + E) log V) overall.
A binary search tree that has degenerated into a straight chain, with every node having only one child, gives a search time of
1. O(log n)
2. O(n)
3. O(n log n)
4. O(1)
Show answer
Answer: B — O(n)
A tree degenerated into a chain has depth n, so a search may have to walk every node exactly as a linked list would, giving O(n) rather than the O(log n) a balanced tree would give.
Which of the following sorting algorithms are stable in their standard implementation (equal elements keep their relative order)?
1. Mergesort
2. Standard (in-place) quicksort
3. Insertion sort
4. Selection sort
Show answer
Answer: A — Mergesort; C — Insertion sort
Mergesort's merge step and insertion sort's shifting both preserve the original order of equal elements; standard in-place quicksort's partitioning and selection sort's long-distance swaps do not guarantee this.