Exam practice

• Correctness: does it give the right answer for every input, including edge cases? Example: a binary search must find the first and last items and say when an item isn’t there; test cases check it.
• Efficiency: how much work does it do, in steps and memory, especially as the data grows? Example: merge sort makes about 9,000 comparisons for 1,000 items, bubble sort about 500,000.
• Clarity: how easy is it to read, check and change? Example: a loop that adds 1 to n is obvious; the formula n(n + 1) ÷ 2 is shorter but needs a comment saying why it is right.

Constant work doesn’t change; linear doubles with each doubling; quadratic becomes 4 times as much (2 × 2), so 4,000 items take 16 times the work of 1,000.

Each match is a pair of teams: 30 × 29 ÷ 2 = 435 matches. With 60 teams: 60 × 59 ÷ 2 = 1,770 matches, about 4 times as many (1,770 ÷ 435 ≈ 4.07). Doubling the teams about quadruples the matches: quadratic growth, O(n²).

6 comparisons for 7 numbers (the most possible, 7 − 1).

• Start: [47] [12] [90] [33] [68] [5] [21] [74]: 8 piles of one.
• Round 1 (4 merges of 1 + 1): [12, 47] [33, 90] [5, 68] [21, 74]: 4 comparisons.
• Round 2: [12, 47] with [33, 90]: 12/33 → 12, 47/33 → 33, 47/90 → 47, then 90: 3 comparisons → [12, 33, 47, 90]. [5, 68] with [21, 74]: 5/21 → 5, 68/21 → 21, 68/74 → 68, then 74: 3 comparisons → [5, 21, 68, 74]. 6 comparisons.
• Round 3: [12, 33, 47, 90] with [5, 21, 68, 74]: 12/5 → 5, 12/21 → 12, 33/21 → 21, 33/68 → 33, 47/68 → 47, 90/68 → 68, 90/74 → 74, then 90: 7 comparisons → [5, 12, 21, 33, 47, 68, 74, 90].

In all, 4 + 6 + 7 = 17 comparisons in 3 rounds.

Step 1: StartStep 2: Read the list of n numbersStep 3: Set i = 1Step 4: Is i < n?        Yes: go to Step 5        No: Display "in order", go to Step 7Step 5: Is number i > number i + 1?        Yes: Display "not in order", go to Step 7        No: go to Step 6Step 6: Set i = i + 1, go to Step 4Step 7: Stop

It compares each pair of neighbors once, so at most n − 1 comparisons (when the list is in order, or only the last pair is wrong). That is linear growth, O(n). (Here the numbers are counted from 1, as in everyday speech; in Python they would be positions 0 to n − 1.)

A deterministic algorithm does the same steps and gives the same output every time it gets the same input. Example: binary search, or merge sort.
A random algorithm makes some of its choices by chance (random numbers), so its steps, and sometimes its answer, can differ from run to run on the same input. Example: quicksort with a random pivot, or estimating π by dropping random dots.
One advantage (either is enough): it can give a good answer quickly where an exact one would take far too long (Monte Carlo); or no particular input can make it slow every time (random quicksort, which is fast on average for every list, even one already sorted).

Every pair: 1,500 × 1,499 ÷ 2 = 1,124,250 comparisons at most (quadratic).
Faster: go through the students once, keeping each birthday seen in a dictionary (the birthday as the key). For each student, if their birthday is already a key, two students share it; otherwise add it. That is at most 1,500 dictionary looks, linear. (With only 366 possible birthdays, a shared one is in fact certain long before the end: a dictionary can hold at most 366 different birthdays, so the 367th student must share one.)

30,000 is 3 times 10,000. Quadratic: 3 × 3 = 9 times the work, so about 27 seconds. Linear: 3 times the work, about 9 seconds.

• a.It prints 2: "tea" and "momo" are in both lists.
• b.It counts how many items of a are also in b (each item of a against each of b). The inner loop runs len(b) times for each item of a: about len(a) × len(b) comparisons, quadratic when both lists are about the same length.
• c.Put the items of b into a dictionary first, then look up each item of a:

def count_matches(a, b):    in_b = {}    for y in b:        in_b[y] = True    count = 0    for x in a:        if x in in_b:            count = count + 1    return count print(count_matches(["tea", "momo", "chiya"], ["momo", "tea", "lassi", "sel roti"]))

2

Now each list is gone through once, and each look-up is constant time: about len(a) + len(b) steps, linear. (One difference: if b held "tea" twice, the first version would count it twice; the dictionary keeps it once. Say which you want before you choose.)

An exponential algorithm’s work doubles each time one item is added: 2ⁿ steps for n items. At a billion steps a second, 30 items (about a billion steps) take about a second; 40 items take about 18 minutes; 50 items about 13 days; 60 items about 37 years; 100 items far longer than the age of the universe. A computer 1,000 times faster only adds about 10 items (2¹⁰ = 1,024) to what can be done in the same time. Faster computers barely help; only a better algorithm, if one exists, does.

• The lists are different sizes: Q did more work because it had 10 times as many items.
• The devices are different: a phone and a computer run at different speeds, so the times say more about the devices than the sorts.
• Each was timed only once: other apps, and a slow first run, can change a single time a lot.

(Also: the lists could be in different orders; a nearly sorted list is easy for some sorts.)
Properly: give both sorts copies of the same lists, on the same computer, time each several times and take the middle time, and repeat for growing sizes (say 500, 1,000, 2,000, 4,000) to see how each one’s time grows.