Python 3.17 Algorithmic Efficiency

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

Popcorn Hack 1: Does One Method Always Win?

For target 3 in [3, 6, 9, 12, 15, 18, 21], linear search finds the target immediately in 1 check, while binary search takes 3 checks (12, 6, then 3). Linear search wins on this particular input, which shows why one easy best-case target is not enough to judge an algorithm overall.

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
# These counts come from tracing both searches on the same sorted list.
linear_steps = 1
binary_steps = 3

# Print both counts so the comparison is visible.
print("Linear search checks:", linear_steps)
print("Binary search checks:", binary_steps)
print("Fewer checks for this target: linear search")

Python Java JavaScript Pseudocode 14px 16px 18px 20px

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 worst-case work doubles from 1000 to 2000. Binary search grows only from 10 to 11 checks. For many searches on a large list that is already sorted, binary search is the better choice because its work grows much more slowly.

Code Runner Challenge

3.17 Popcorn 2 - compare search growth

View IPYNB Source

# CODE_RUNNER: 3.17 Popcorn 2 - compare search growth
# Comparing both sizes shows how linear work doubles while binary-search work grows only slightly.
import math

# Test both required input sizes from the lesson.
for n in [1000, 2000]:
    linear_steps = n
    binary_steps = math.floor(math.log2(n)) + 1
    print("List size:", n)
    print("Linear search: up to", linear_steps, "checks")
    print("Binary search: up to", binary_steps, "checks")
    print()

Python Java JavaScript Pseudocode 14px 16px 18px 20px

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Popcorn Hack 3: Small Input, Big Difference

At n = 10, the estimates are linear 10, quadratic 100, and exponential 1024. At n = 20, they are linear 20, quadratic 400, and exponential 1,048,576. Exponential growth increases the fastest, so the linear approach is the first one I would investigate for a large input when all three solve the same task correctly.

Code Runner Challenge

3.17 Popcorn 3 - compare growth patterns

View IPYNB Source

# CODE_RUNNER: 3.17 Popcorn 3 - compare growth patterns
# Printing all three estimates side by side makes the different growth rates easy to compare.
# Evaluate the three work estimates for both lesson input sizes.
for n in [10, 20]:
    print("Input size:", n)
    print("Linear work:", n)
    print("Quadratic work:", n ** 2)
    print("Exponential work:", 2 ** n)
    print()

Python Java JavaScript Pseudocode 14px 16px 18px 20px

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Popcorn Hack 4: Explain the Tradeoff

Someone might choose the nearest remaining errand instead of checking every possible order because the heuristic can produce a useful route much sooner. The tradeoff is that it does not guarantee the shortest possible route.

Knowledge Check

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

1. B: Efficiency compares work and memory as input grows.
2. A: Binary search can discard half because the list is sorted.
3. C: Growth from 10 to 11 checks while input doubles is logarithmic.
4. B: A small fast test does not prove an exponential algorithm is practical for a much larger input.

Homework Hack: Choose an Algorithm

The list is already sorted, so the required comparison uses 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
# The same calculation is repeated for each list size so the recommendation is based on consistent evidence.
import math

# Run the same worst-case comparison for every required input size.
for n in [100, 1000, 10000]:
    linear_steps = n
    binary_steps = math.floor(math.log2(n)) + 1
    print("List size:", n)
    print("Linear search worst-case checks:", linear_steps)
    print("Binary search worst-case checks:", binary_steps)
    print()

Python Java JavaScript Pseudocode 14px 16px 18px 20px

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Homework Recommendation

1. For many searches on an already sorted list, I would choose binary search. The worst-case counts are 7 vs 100 for 100 items, 10 vs 1000 for 1,000 items, and 14 vs 10,000 for 10,000 items. Binary search grows much more slowly as the list gets larger.

2. If the list is unsorted and I only need one search, linear search may be better. Binary search requires sorted data, so sorting first adds preparation work that may not be worthwhile for only one lookup.

3. Yes, linear search can beat binary search on a particular target. For example, if the target is the first item, linear search can find it in one check while binary search may inspect several middle values first.

4. Keeping a separate sorted copy requires extra memory. The program must store another version of the list in addition to the original.