Quiz · Hard
Time and space complexity of arrays, linked lists, stacks, queues, hash tables, trees, heaps and graphs, plus analyzing loops and sorting algorithms. Useful for CS courses and coding interviews.
What is the time complexity of reading arr[i] from an array?
Array elements sit in contiguous memory, so the address is computed directly (base + i × element size). No scanning is needed, whatever the index.
What is the worst-case time complexity of binary search on a sorted array of n elements?
Each comparison halves the remaining range, so at most about steps: around 20 for a million items. It only works if the array is sorted; linear search is .
What is the time complexity of this code?
total = 0
for i in range(n):
for j in range(i, n):
total += 1The inner loop runs n, n − 1, ..., 1 times, for a total of . Big-O drops the constant and lower-order terms, leaving . Starting j at i halves the work but does not change the order of growth.
What is the time complexity of this loop?
i = 1
while i < n:
i *= 2i takes the values 1, 2, 4, 8, ..., so the loop runs about times. Any loop that multiplies or divides its counter by a constant is logarithmic.
What are the average and worst-case lookup times for a hash table?
Average , worst
Average , worst
Average , worst
Average , worst
A good hash function spreads keys evenly, so lookups are constant time on average. If many keys collide into one bucket, a lookup degrades to scanning them all, which is .
Starting with an empty stack: push 1, push 2, push 3, pop, push 4, pop. Which values were popped, in order?
1, then 2
3, then 2
3, then 4
4, then 3
A stack is last in, first out. The first pop removes 3 (the most recent push). Then 4 is pushed and immediately popped. The stack now holds 1, 2.
Which data structure does breadth-first search (BFS) use to decide which node to visit next?
A queue
A stack
A min-heap
A hash table
BFS visits nodes level by level, so it needs first in, first out order: a queue. Depth-first search uses a stack, or the call stack through recursion. A visited set (often a hash table) is used too, but it does not set the order.
For a singly linked list with a head pointer, what are the costs of inserting at the head and of accessing the k-th element?
Insert at head ; access k-th
Both
Both
Insert at head ; access k-th
Inserting at the head is just relinking a pointer. There is no index arithmetic, so reaching the k-th node means walking k links, which is in the worst case. Arrays have the opposite trade-off.
Keys 1, 2, 3, ..., n are inserted in that order into a plain (unbalanced) binary search tree. What is the worst-case search time?
Each new key goes to the right of the last one, so the tree turns into a linked list of height n. Self-balancing trees (AVL, red-black) keep the height at .
Which data structure is the standard way to implement a priority queue?
A sorted linked list
A stack
A plain array searched each time
A binary heap
A binary heap gives insert and remove-min, and peek at the minimum. A sorted linked list makes removal fast but insertion .
Which sorting algorithm has a worst-case time complexity of O(n²)?
Quicksort (with poor pivot choices)
Merge sort
Heapsort
None of these comparison sorts
Quicksort averages , but if the pivot is always the smallest or largest element (for example, the first element of an already sorted array), it degrades to . Merge sort and heapsort are in every case.
The keys 5, 3, 8, 1, 4 are inserted in that order into an empty binary search tree. What is the preorder traversal?
1, 3, 4, 5, 8
1, 4, 3, 8, 5
5, 3, 1, 4, 8
5, 3, 8, 1, 4
The tree is 5 at the root, 3 on its left (with children 1 and 4) and 8 on its right. Preorder visits root, left subtree, right subtree: 5, 3, 1, 4, 8. 1, 3, 4, 5, 8 is the inorder traversal (always sorted for a BST), and 1, 4, 3, 8, 5 is postorder.
What is the time complexity of the naive recursive Fibonacci function fib(n) = fib(n-1) + fib(n-2)?
Exponential,
Each call spawns two more and the same values are recomputed over and over, so the call tree grows exponentially (more precisely about ). Memoization or a simple loop brings it down to .
Appending to a dynamic array (Python list, Java ArrayList) occasionally triggers a full copy into a bigger array. What is the amortized cost of append?
The capacity grows by a constant factor (for example doubling), so copies get rarer as the array grows. Over n appends, the total copying is , which averages to per append. A single append can still take .
A graph has V vertices and E edges. How much space does an adjacency list use?
Each vertex has a list, and each edge appears once (directed) or twice (undirected). An adjacency matrix always uses , which is wasteful for sparse graphs but gives edge lookup.
Why can Dijkstra's algorithm give wrong answers on some graphs?
It only works on undirected graphs
It cannot handle cycles
It assumes no edge has a negative weight
It needs all edge weights to be equal
Dijkstra finalizes a node once it is popped from the priority queue, assuming no later path can be shorter. A negative edge can break that assumption. Bellman-Ford handles negative weights (and detects negative cycles).