🎯 HOOK

The Lost Key Problem

You dropped your key somewhere in a long hallway with 100 doors. You need to check each door to find it. If you double the hallway length to 200 doors, how does your search time change?

🧪 EXPLORE

Watch Linear Search in Action

Adjust the list size and start a search. Notice how many checks are needed!

Searching for: ?
Items Checked
0
Total Items
10
Time
0ms

Observe: When you double the list size, the worst-case checks also double. That's the hallmark of O(n)!

💡 EXPLAIN

What is O(n)?

Linear time means the operations grow in direct proportion to the input size (n).

🚶

Think of it like walking a line

  • ✓ Linear search through an array
  • ✓ Counting items in a list
  • ✓ Finding max/min value
  • ✓ Summing all elements

The straight diagonal line shows direct proportionality: 10 items → 10 operations, 100 items → 100 operations, 1000 items → 1000 operations.

✓ When O(n) is Good

  • • Small to medium datasets
  • • One-time operations
  • • When you must check everything

⚠️ When to Optimize

  • • Very large datasets (millions)
  • • Repeated lookups (use hash map)
  • • Real-time systems with strict limits
✏️ PRACTICE

Test Your Understanding

1. Which operation is O(n)?

2. An algorithm processes 1000 items in 2 seconds. How long for 5000 items?

(Assume O(n) complexity)

3. What's the complexity of this code?

def find_max(arr):
  max_val = arr[0]
  for num in arr:
    if num > max_val:
      max_val = num
  return max_val

4. True or False: O(n) is always slow

5. Match the scenario to the correct statement

Scenario: Checking if a name exists in an unsorted list of 1 million names

6. Predict the growth

Use the simulator above. Set list size to 10, then 20. How do the checks change?

7. Code challenge: What's the complexity?

function printPairs(arr) {
def print_pairs(arr):
  for item in arr:
    print(item)
  for item in arr:
    print(item)
🤔 REFLECT

Think Deeper

💭 When is O(n) unavoidable?

💭 O(n) vs O(1): When would you use a hash map instead of an array?

🎉

Well Done!

You've mastered O(n) linear time — algorithms that scale in direct proportion to input size.