Python 3.17 Algorithmic Efficiency

Completed all four Popcorn Hacks, the Knowledge Check, and the Homework Hack comparing linear and binary search.

Popcorn Hack 1: Does One Method Always Win?

Target 3 in [3, 6, 9, 12, 15, 18, 21]: linear search checks 3 first and is done in 1 check. Binary search starts in the middle, so it checks 12, then 6, then 3, which is 3 checks. Here linear search wins, so one easy target isn’t enough to judge which algorithm is better.

Code Runner Challenge

3.17 Popcorn 1 - compare checks for target 3

View IPYNB Source 
# CODE_RUNNER: 3.17 Popcorn 1 - compare checks for target 3
numbers = [3, 6, 9, 12, 15, 18, 21]
target = 3

# Linear search: look at each item from the start.
linear_checks = 0
for n in numbers:
    linear_checks = linear_checks + 1
    if n == target:
        break

# Binary search traced by hand: 12 -> 6 -> 3
binary_checks = 3

print("Linear search checks:", linear_checks)
print("Binary search checks:", binary_checks)
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Popcorn Hack 2: Compare Growth

When n doubles from 1000 to 2000, linear search’s worst case doubles from 1000 to 2000 checks. Binary search only goes from 10 to 11. For lots of searches on a big sorted list, binary search is the better choice.

Code Runner Challenge

3.17 Popcorn 2 - compare search growth

View IPYNB Source 
# CODE_RUNNER: 3.17 Popcorn 2 - compare search growth
import math

for n in [1000, 2000]:
    binary = math.floor(math.log2(n)) + 1
    print("n =", n, "| linear:", n, "| binary:", binary)
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Popcorn Hack 3: Small Input, Big Difference

At n = 10: linear 10, quadratic 100, exponential 1024. At n = 20: linear 20, quadratic 400, exponential 1,048,576. Exponential grows the fastest by far, so for a big input I’d look at the linear approach first.

Code Runner Challenge

3.17 Popcorn 3 - compare growth patterns

View IPYNB Source 
# CODE_RUNNER: 3.17 Popcorn 3 - compare growth patterns
for n in [10, 20]:
    print("n =", n, "| linear:", n, "| quadratic:", n * n, "| exponential:", 2 ** n)
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Popcorn Hack 4: Explain the Tradeoff

Going to the nearest errand next is a heuristic: it gives a pretty good route very quickly instead of testing every possible order. The tradeoff is that it does not guarantee the shortest route.

Knowledge Check

Answers: B, A, C, B
Score: 4/4

  1. B: Efficiency compares how much work and memory an algorithm needs as the input grows.
  2. A: Binary search can skip half the list each step because the list is sorted.
  3. C: Going from 10 to 11 checks when the input doubles is logarithmic growth.
  4. B: A fast test on a small input doesn’t prove an exponential algorithm works for a big one.

Homework Hack: Choose an Algorithm

The list is already sorted. I compared worst-case checks for n = 100, 1000, and 10000.

Code Runner Challenge

3.17 Homework - compare search counts for three list sizes

View IPYNB Source 
# CODE_RUNNER: 3.17 Homework - compare search counts for three list sizes
import math

for n in [100, 1000, 10000]:
    linear = n
    binary = math.floor(math.log2(n)) + 1
    print("List size", n, "-> linear:", linear, "checks | binary:", binary, "checks")
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Homework Recommendation

  1. Many searches on a sorted list: binary search. Worst case is 7 vs 100 checks at 100 items, 10 vs 1000 at 1,000 items, and 14 vs 10,000 at 10,000 items.

  2. Unsorted list, only one search: linear search can be better. Binary search needs sorted data, and sorting first is extra work that isn’t worth it for one lookup.

  3. Yes, linear search can win on a specific target. If the target is the first item, linear search needs only 1 check.

  4. A separate sorted copy uses extra memory, because the program now stores two versions of the list.