Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 2
Complexity and the Array · control flow, functions, errors (Lecture 02, Lab 02)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
f(n) = 3n2 + 5n + 2 is:
Keep the fastest-growing term, drop its constant: 3n2 → n2. It is also O(n3), but not Θ(n3) (c) — Θ is a tight bound.
-
Which statement is true?
n ≤ 1 · n2 for all n ≥ 1. O is an upper bound, so a slower-growing function is O of a faster one. (a) and (d) put a faster function under a slower one; (b) claims n grows at least as fast as n2.
-
f(n) = O(g(n)) means:
Constants you choose, and only from some n0 on. (b) has no constant and no n0; (c) is equality, not a bound; (d) is the definition of Ω.
-
In the worst case, how many comparisons does linear search make on an array of n elements?
Worst case: the target is last or absent, so every element is compared once.
-
The target is present and equally likely to be at any of the n positions. On average, how many comparisons does linear search make?
(1 + 2 + … + n)/n = (n+1)/2. Still O(n) — half is a constant.
-
What is the running time of this loop?
i = n while i > 1: i = i // 2Halving until 1 takes about log2 n steps. Θ(n/2) (d) would be subtracting, not dividing — and it is just Θ(n) anyway.
-
What is the running time?
for i in range(n): for j in range(i): count += 10 + 1 + … + (n-1) = n(n-1)/2. The answer must be a function of n only, so (c) is not an answer.
-
What is the running time?
for i in range(n): for j in range(5): count += 1The inner loop is a constant 5: 5n = Θ(n). Nested loops multiply their iteration counts, not their nesting depth.
-
For a Python
listof n items,x in valuescosts:A list is an array;
inchecks items one by one. Sets and dicts are the hash tables (a). -
Which Python
listoperation is O(1) (amortised)?appendwrites at the end — nothing moves — and the occasional resize averages out (Week 4). The other three shift or search: O(n). -
Why is reading
a[i]from an array O(1)?Address arithmetic. It has nothing to do with order (a) or caching (b).
-
A partly filled array has size 6. How many elements must move to insert a new value at index 2?
Slots 2, 3, 4, 5 move right: size − index = 6 − 2 = 4.
-
When inserting into an array, the elements after the gap must be shifted right. In which order?
Moving right, start at the right, or you overwrite values before you move them (see W2-S2).
-
a = Array(4), thena[-1]. What happens?The course
Arrayhas no negative indices, like C. -
a = Array(5), thena[0] = 7. What islen(a)?lenis the capacity, fixed at creation. Tracking how many slots are in use is your job. -
A 3 × 4 matrix (3 rows, 4 columns) is stored flat in row-major order. At which index is element (2, 1)?
r × cols + c = 2 × 4 + 1 = 9.
-
What extra space does
reverse_in_place(arr)need (swap from both ends, no second array)?Two indices and one temporary for the swap, whatever n is.
-
Under the course storage rule (Lecture 02), which of these is not allowed?
A structure may not store its data in a Python
list. (a) and (b) build on the student's own structures — allowed; (d) is a list used as a return value — the interface, allowed. -
Python's built-in
listis best described as:A block of references plus a size and a capacity; it grows by copying into a bigger block.
-
An O(n) loop is followed by an O(n2) loop. The whole is:
Sequence adds: O(n + n2) = O(n2).
-
valuesis a Python list of n items. The cost of:for i in range(len(values)): if values[i] in values[i + 1:]: return TrueEach iteration hides two O(n) operations: the slice copies up to n items and
insearches them. n iterations of O(n) work. -
When does the
elseblock of aforloop run?Think of it as "no break".
-
Given
def f(a, L=[]): L.append(a) return Lwhat does
f(1)thenprint(f(2))print?The default list is created once, when
defruns, and shared by every call that uses it. -
What is the value of
0 or 'x' and ''?andbinds tighter:0 or ('x' and '').'x' and ''gives''(the last value looked at);0 or ''gives''. -
list(range(2, 11, 3))is:Start 2, step 3, stop before 11: 2, 5, 8.
-
What does
print(g())print?def g(): try: return 1 finally: print("bye")return 1is decided, thenfinallyruns (printingbye) before the function actually returns; thenprintshows1. -
In the RAM model of Lecture 02, which of these is not one basic step?
inon a list walks it comparing item by item, O(n) — a hidden loop (Rule 5). One slot read or write (a), one comparison of small numbers (c) and the call itself (d) each take constant time. -
An algorithm does n2 basic steps and takes 1 second at n = 10,000. About how long will it take at n = 100,000, on the same machine?
Ten times the input, squared: 102 = 100 times the work, so about 100 seconds. 10 seconds (a) is what an O(n) algorithm would take; 1,000 (b) would be n3.
-
Algorithm A does 1000n steps; algorithm B does n2 steps. Which statement is true?
1000n < n2 exactly when n > 1000. Big-O describes growth for large n, so (b) is wrong for small n; (c) ignores that n2 overtakes any 1000n; being polynomials (d) says nothing about which is smaller.
-
Which sentence about linear search is correct?
"Best/worst case" says which input; O, Ω, Θ say what kind of bound. The two are independent, so (a) and (b) confuse them. (d) is false: it stops at the first match, so one comparison is enough when the target is first.
-
What is the running time of this loop?
i = 0 while i * i < n: i += 1The loop stops when i2 ≥ n, that is after about √n steps (n = 1,000,000 gives i = 1,000). It neither halves (a) nor walks all the way to n (c).
-
A recursive
total(values)makes one call per element and creates no new data. Its extra space is:Recursion uses space: n calls deep means n frames waiting at once. Creating no data (a) is not the same as using no memory — and Python stops at about 1,000 frames.
-
A partly filled
Arrayhas size 7. How many elements move duringremove_at(arr, 7, 2)?Slots 3 to 6 move left: size − index − 1 = 7 − 2 − 1 = 4. Five (b) is the count for
insert_atat index 2. -
remove_atends witharr[size - 1] = None. Why?After the shift, slot
size - 1still holds a copy of the last reference. Clearing it means nothing reads a stale value, and the object can be freed.len(arr)is the fixed capacity and never changes (a); the order (b) was already right after the shift. -
In C, after
int a[6];, the statementa[6] = 0;:C does not check indices:
a[6]is base + 6 × 4, the memory right after the array. No error is raised (a), and an array cannot grow (b) or wrap (c). The courseArraychecks, and raisesIndexError. -
One Python array can hold an
int, astrand alist, and still index in O(1). Why?The slot holds a reference to the object, not the object; every reference is 8 bytes on a 64-bit machine, so base + i × 8 still works. The objects themselves live elsewhere, at any size — no sorting (a) or padding (c).
-
a = Array(3), thena[0:2]. What happens?A slice is a copy, O(k), dressed as one step, so the course
Arrayrefuses it: "Array does not support slicing; copy with a loop". -
arrholds[1, 2, 3, 4, 5, 6]. What does it hold afterrotate_left(arr, 8)?rotate_leftfirst doesk %= n: 8 mod 6 = 2, so it rotates left by 2. (a) would be right only for k = 6 or 12; (d) is a rotation to the right by 2. -
merge_sorted(a, b)takes the front ofawhena[i] <= b[j]. Why<=rather than<?With
<, an equal value frombwould be taken first, swapping the order of equal values; the output would still be sorted (a), with no error (b) and no endless loop (c). Keeping equal values in their original order is stability (Week 10). -
A 3 × 4 matrix holding the values 0 to 11 row by row is stored flat in row-major order.
transpose_flat(arr, 3, 4)returns the 4 × 3 transpose, also row-major. At which index of the result is the value 1?1 is at (0, 1) in the 3 × 4 matrix, so at (1, 0) in the 4 × 3 transpose: 1 × 3 + 0 = 3. The result is
[0, 4, 8, 1, 5, 9, …]. -
"Any sort that works only by comparing elements needs Ω(n log n) comparisons in the worst case." This means:
It is a lower bound on the problem for comparison sorts. Counting sort (Week 9) uses the values as indices and never compares, so the bound does not apply to it (b). Ω is "at least", not "exactly" (c), and not an upper bound (d).
-
How many pairs does
is_sorted(arr)compare whenarrholds[5, 1, 2, 3, 4, 6, 7, 8]?It compares 5 with 1, finds them out of order and returns
Falseat once: O(1), the best case. Seven (a) is the number of pairs in a sorted array of 8. -
What happens when
increment()is called?count = 0 def increment(): count = count + 1The assignment makes
countlocal for the whole function, so reading it on the right-hand side finds a local with no value yet. Python does not fall back to the global (a, c), and the error is more specific than aNameError(b). -
What does
print(users)show?users = ['guest1', 'guest2', 'ali', 'guest3'] for u in users: if u.startswith('guest'): users.remove(u) print(users)Removing
'guest1'shifts every item left, so the loop's next position holds'ali':'guest2'is skipped.'guest3'is then removed. A list does not raise (d) — dicts and sets do. Loop over a copy, or build a new list.
37 marks
Written questions
10 written questions (37 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 37
-
Big-O throws away constant factors and lower-order terms. Explain why each is thrown away, give one situation where doing so is misleading, and explain how measuring complements counting.
Model answer and marking points
- Lower-order terms stop mattering as n grows: in 1/2 n2 - 1/2 n, the n2 term is 99.9% of the total by n = 1,000.
- Constant factors are not properties of the algorithm: they change with the machine, the language and how you count steps. What stays the same everywhere is the shape of growth.
- Misleading when n is small, or constants are huge: a 1000n algorithm is worse than an n2 one for every n < 1,000; linear search beats binary search on tiny arrays.
- Measuring (
viz.complexity.measure) shows the constants and the crossover point that Big-O hides; counting shows the shape that one machine's timings cannot prove. You need both.
-
Define O, Ω and Θ precisely. For f(n) = 3n2 + 2n, give one true statement using each, and one true but uninformative O statement.
Model answer and marking points
- f = O(g): there exist c > 0, n0 with f(n) ≤ c g(n) for all n ≥ n0 — an upper bound.
- f = Ω(g): there exist c > 0, n0 with f(n) ≥ c g(n) for all n ≥ n0 — a lower bound.
- f = Θ(g): both — c1 g(n) ≤ f(n) ≤ c2 g(n) eventually — a tight bound.
- For 3n2 + 2n: it is O(n2), Ω(n2), Θ(n2); it is also Ω(n). True but uninformative: 3n2 + 2n = O(n3) (or O(2n)).
-
Describe the best, worst and average case of linear search, with the number of comparisons for each. Which one does "linear search is O(n)" usually refer to, and why is that the default?
Model answer and marking points
- Best: the target is the first element — 1 comparison, O(1).
- Worst: last or absent — n comparisons, O(n).
- Average (present, uniformly placed): (n+1)/2, still O(n) — and the average needs a stated assumption about the inputs.
- "Linear search is O(n)" means the worst case: it is a guarantee that holds for every input of size n, needs no assumption, and is what you plan capacity around.
-
Explain why indexing an array is O(1) but inserting into the middle is O(n). What does the fact that an array has a fixed size force you to do when it fills up, and what does that cost?
Model answer and marking points
- An array is contiguous, equal-sized slots, so the address of
a[i]is base + i × size: one multiplication and one addition, independent of n → O(1). - Inserting at index i in an array of size n needs every element from i to the end moved one place right: n - i moves, n in the worst case → O(n).
- Fixed size: the memory after the block may belong to something else, so the array cannot grow in place. When it is full, you must allocate a new, larger array and copy every element across: O(n) for that operation.
- (Doubling the capacity each time makes appends O(1) amortised — Week 4.)
- An array is contiguous, equal-sized slots, so the address of
-
State the course storage rule from Lecture 02. Give the reason for it, list what remains allowed, and show how two structures from later in the course follow it.
Model answer and marking points
- Rule: a data structure in
dsa/stores its data only in the courseArray, in node objects, or in another structure the student has built — never in a Pythonlist,dict,setordeque. - Reason: those built-ins hide exactly the costs the course teaches — one short call like
insert(0, x),pop(0)orx in valuesis an O(n) algorithm someone else wrote. Building on a bare array makes every cost visible and yours. - Still allowed: lists as function inputs and return values; lists in tests; plain local variables and tuples.
- Examples, any two:
Stackon the student'sDynamicArray;CircularQueueon anArray;ChainingHashMapas anArrayofEntrychains;Graphon the student's hash map andDynamicArrays;MinHeapon aDynamicArray.
- Rule: a data structure in
-
Compare Python's
list,array.array,numpy.ndarrayand actypesarray on: can it grow, what it holds, and whether it hides costs. Why is the courseArraybuilt onctypes?Model answer and marking points
Grows? Holds Hides the cost? listyes (dynamic array) references to any objects yes array.arrayyes packed numbers of one type yes numpy.ndarrayno packed numbers of one type yes — whole-array operations run in C ctypesarrayno C values or references no — index and assign only A
ctypesarray of object references is a genuine fixed-size C array that can hold any Python object. The course wraps it, adds bounds checking, and offers nothing else — so every other operation must be written, and priced, by the student. -
valuesis a Python list of n numbers. Give the running time of each numbered part of this function, justify each with one of the five rules, and give the total. Why is part (3) not O(n2), although it hides a slice and anininside a loop?def report(values): total = 0 for v in values: # (1) total += v i = len(values) while i > 1: # (2) i //= 2 for v in values: # (3) if v in values[:10]: total -= v return totalModel answer and marking points
- (1) One pass over n items with an O(1) body: Rule 2, Θ(n).
- (2) i is halved until it reaches 1: Rule 4, Θ(log n).
- (3) n iterations (Rule 2); the body hides a slice and an
in(Rule 5), but the slice copies at most 10 items andinsearches at most 10 — a constant, not n. So the body is O(1) and the loop is Θ(n). A hidden loop costs what it actually walks: here a fixed 10, not the whole list. - Total, by Rule 1: Θ(n + log n + n) = Θ(n). (Timing it confirms this: doubling n doubles the time.)
-
Define the auxiliary space of an algorithm. Give the extra space of
reverse_in_place,resized(arr, 2n),merge_sorted(a, b)and a recursivetotal(values), with a reason for each. Why does recursion use space even when it creates no data, and what limit does Python put on it?Model answer and marking points
- Auxiliary space: the memory an algorithm needs beyond its input, as a function of n.
reverse_in_place: two indices and a swap — O(1).resized(arr, 2n): a new array of 2n slots — O(n).merge_sorted(a, b): the output array — O(n + m).- Recursive
total(values): O(n) — every call that has not yet returned keeps a frame (its arguments, its local variables, where to return to) on the call stack, n frames at the deepest point. - Python stops recursion at about 1,000 frames (
RecursionError), so a recursion n deep fails for large n; a loop with O(1) space does not. Time and space can be traded: merge sort uses O(n) extra space for its O(n log n) time.
-
Explain row-major order. A 5 × 7 matrix (5 rows, 7 columns) is stored flat in row-major order: at which flat index is element (3, 4), and which (row, column) is at flat index 30? Why is reaching (r, c) still O(1)?
Model answer and marking points
- Row-major: the rows are stored one after another in one flat array, so element (r, c) is at index r × cols + c.
- (3, 4) in a 5 × 7 matrix: 3 × 7 + 4 = 25. Index 30: row 30 // 7 = 4, column 30 % 7 = 2, so (4, 2).
- Reaching (r, c) is one multiplication and one addition, then one O(1) array index — whatever the matrix size.
-
The course
Arrayrefuses negative indices, slicing andappend. For each refusal, explain why it is deliberate and what you write instead. Then explain the difference betweenlen(a)and the size of a partly filled array, and who keeps track of each.Model answer and marking points
- No negative indices: an index is an offset from the base, and there is nothing before the base (as in C). You compute
size - 1for the last element;DynamicArray(Week 4) adds negative indexing as the translationi + size. - No slicing: a slice is a copy, O(k), that looks like one step. You write the copying loop and see the cost.
- No
append: an array cannot grow; that is the definition. To make room you allocate a biggerArrayand copy —resized, the dynamic array's one move. len(a)is the capacity, fixed when theArrayis created; the size — how many slots from index 0 hold real data — is kept by your code, in a separate variable (insert_atandremove_attake it and the caller updates it). That split is what the dynamic array is built on.
- No negative indices: an index is an offset from the base, and there is nothing before the base (as in C). You compute