Purpose: Self-check on linear/binary search, sorting algorithms, and Big-O complexity. Instant feedback. Python 3.
Score: 0 / 12
Question 1 — Linear search count
In the worst case, how many comparisons does linear search make on a list of 1000 items?
Solution:
Worst case: target is at the end (or absent). Linear search inspects every item: 1000 comparisons. This is O(n).
Question 2 — Binary search count
In the worst case, how many comparisons does binary search need on a sorted list of 1024 items?
Solution:
1024 = 2¹°. Binary search halves the search space each step: ceiling(log₂1024) = 10 comparisons. This is O(log n).
Question 3 — Binary search precondition
Which precondition must hold for binary search to give a correct answer?
Solution:
The list must be sorted. The algorithm relies on comparing to the midpoint; if the list isn't ordered, the wrong half is eliminated.
Question 4 — Bubble sort trace
After ONE complete pass of bubble sort (ascending) on [5, 2, 9, 1, 7], what does the list look like?
Solution:
Compare/swap adjacent pairs left-to-right: 5,2 → swap → [2,5,9,1,7] 5,9 → no → [2,5,9,1,7] 9,1 → swap → [2,5,1,9,7] 9,7 → swap → [2,5,1,7,9]. Largest "bubbled" to the end.
Question 5 — Big-O of bubble sort
What is the worst-case time complexity of bubble sort?
Solution:
Bubble sort's nested loops give O(n²) in the worst (and average) case.
Question 6 — Merge sort complexity
Average-case complexity of merge sort?
Solution:
Merge sort divides into halves (log n levels) and does linear merging at each level: O(n log n). This is the same in best, average, and worst cases.
Question 7 — Selection sort trace
Selection sort, ascending. After the FIRST iteration on [64, 25, 12, 22, 11], what is the list?
Solution:
Find min (11) and swap with index 0: [11, 25, 12, 22, 64].
Question 8 — Order growth rates
For very large n, which is fastest (smallest)?
Solution:
Order from fast to slow for large n: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). O(log n) is fastest of the four listed.
Question 9 — Counting operations
How many times does the inner statement execute?
count = 0
for i in range(n):
for j in range(n):
count += 1
Solution:
Outer runs n times; inner runs n each iteration: n². Big-O is O(n²).
Question 10 — Quicksort pivot
In quicksort with the FIRST element as pivot, what is the worst case input?
Solution:
An already-sorted list (or reverse-sorted) makes the pivot always the smallest (or largest), producing severely unbalanced partitions: O(n²). Random pivot or median-of-three avoids this.
Question 11 — Choose the right algorithm
A teacher has a sorted phone list of 5000 students and needs to look up one student. Which algorithm is best?
Solution:
Already sorted → binary search in ~13 comparisons (log₂5000 ≈ 12.3). Linear is up to 5000.
Question 12 — Insertion sort efficiency
When is insertion sort especially efficient (close to O(n))?
Solution:
On a nearly-sorted list, insertion sort makes few shifts and approaches O(n). This is why it's used as the fallback inside Python's Timsort for small/sorted runs.