Unit 9 • Lesson 5

Efficiency and Big-O Basics

Overview

Not all code runs equally fast — efficiency matters. You'll be introduced to the concept of algorithmic complexity (Big-O notation) and learn simple ways to make your programs faster and more memory-efficient, writing code that scales well.

Intermediate 25–30 min

Next: Working with Dates and Times All Units

What You Will Learn in This Lesson

By the end of this lesson, you will know:

Algorithm efficiency: Why some code runs faster than others.
Big-O notation: How to describe algorithm performance.
Time complexity: How execution time grows with input size.
Common complexities: O(1), O(n), O(n²) and what they mean.
Optimization: Simple ways to make code more efficient.

Why Efficiency Matters

Efficient code runs faster and uses less memory. As your programs handle more data, efficiency becomes crucial.

Real-World Impact

Faster programs = better user experience
Efficient code uses less memory
Scales better with larger datasets
Can handle more users or requests
Saves computational resources

Example: Inefficient vs Efficient

# Inefficient: O(n²) - nested loops
def find_duplicates_slow(items):
    duplicates = []
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                duplicates.append(items[i])
    return duplicates

# Efficient: O(n) - single loop with set
def find_duplicates_fast(items):
    seen = set()
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        seen.add(item)
    return duplicates

Big-O Notation

Big-O notation describes how algorithm performance changes as input size grows. It shows the worst-case scenario and helps you understand scalability.

Understanding Big-O

Big-O notation uses "O" followed by a function that describes how the algorithm's time or space requirements grow. The "n" represents the input size. We focus on the dominant term and ignore constants.

O(1) - Constant Time

Accessing a list element by index. Time doesn't change with input size.

my_list[0]  # Always takes same time

O(n) - Linear Time

Looping through a list once. Time grows proportionally with input size.

for item in my_list:  # Time = n

O(n²) - Quadratic Time

Nested loops. Time grows with the square of input size.

for i in range(n):
    for j in range(n):  # Time = n²

O(log n) - Logarithmic Time

Binary search. Time grows slowly as input increases.

# Binary search halves
# search space each step

Comparing Complexities

# O(1) - Constant
def get_first(items):
    return items[0]  # Always same time

# O(n) - Linear
def find_max(items):
    max_val = items[0]
    for item in items:  # Loops n times
        if item > max_val:
            max_val = item
    return max_val

# O(n²) - Quadratic
def find_duplicates(items):
    duplicates = []
    for i in range(len(items)):      # Outer loop: n
        for j in range(i+1, len(items)):  # Inner loop: n
            if items[i] == items[j]:
                duplicates.append(items[i])
    return duplicates

Complexity Comparison

For n=1000: O(1) = 1 operation, O(n) = 1000 operations, O(n²) = 1,000,000 operations! As data grows, the difference becomes huge.

Optimization Tips

Simple ways to make your code more efficient:

Choose the Right Data Structure

Use sets for membership testing (O(1)) instead of lists (O(n)). Use dictionaries for lookups.

Avoid Nested Loops When Possible

Nested loops create O(n²) complexity. Look for ways to use a single loop or built-in functions.

Use Built-in Functions

Python's built-in functions are often optimized in C. Use max(), min(), sum() instead of writing loops.

Cache Results

If you compute the same value multiple times, store it in a variable instead of recalculating.

Optimization Example

# Slow: O(n²) - nested loops
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i+1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# Fast: O(n) - single loop with set
def has_duplicate_fast(items):
    seen = set()
    for item in items:
        if item in seen:  # O(1) lookup
            return True
        seen.add(item)
    return False

Practice: Understanding Complexity

Try It Yourself

Try identifying the complexity of different operations:

# O(1) - Constant time
items = [1, 2, 3, 4, 5]
first = items[0]  # Always same time
print(f"First item: {first}")

# O(n) - Linear time
for item in items:
    print(item)  # Loops n times

print("\nComplexity: O(1) for access, O(n) for loop")

Press Run to see output

What happened? Accessing an element by index is O(1) - it always takes the same time. Looping through all elements is O(n) - time grows with the list size.

Space Complexity

Big-O can also describe space (memory) usage:

Space Complexity Examples

# O(1) space - constant memory
def get_first(items):
    return items[0]  # Only uses one variable

# O(n) space - memory grows with input
def copy_list(items):
    new_list = []  # Creates new list of size n
    for item in items:
        new_list.append(item)
    return new_list

# O(n²) space - memory grows quadratically
def create_matrix(n):
    matrix = []
    for i in range(n):
        row = [0] * n  # Creates n×n matrix
        matrix.append(row)
    return matrix

Time vs Space

Sometimes you can trade time for space or vice versa:

Time optimization: Use more memory (caching) to speed up calculations
Space optimization: Use more time (recalculating) to save memory
Balance: Choose based on what's more important for your application

Real-World Efficiency Examples

Understanding efficiency helps in real projects:

Example: Finding Duplicates

# O(n²) - Slow for large lists
def has_duplicates_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# O(n) - Fast, uses set for O(1) lookups
def has_duplicates_fast(items):
    seen = set()
    for item in items:
        if item in seen:  # O(1) lookup
            return True
        seen.add(item)
    return False

# For 1000 items:
# Slow version: ~500,000 comparisons
# Fast version: ~1000 operations

Practical Impact

For small datasets (10-100 items), efficiency doesn't matter much. But for large datasets (thousands or millions), choosing the right algorithm can mean the difference between seconds and hours!

Summary

In this lesson, you learned:

Efficiency: Important for performance and scalability
Big-O: Describes how algorithms scale with input size
Common complexities: O(1), O(n), O(n²), O(log n)
Optimization: Choose efficient algorithms and data structures
Space complexity: Memory usage also matters
Real-world impact: Efficiency becomes critical with large datasets

Remember

Don't optimize prematurely! First make your code work correctly, then optimize if needed. But understanding efficiency helps you write better code from the start. When in doubt, use built-in functions and appropriate data structures (sets for membership, dictionaries for lookups).

End-of-Lesson Exercises

Think about these questions to reinforce what you've learned:

Exercise 1: Big-O

What does Big-O notation describe? Give examples of O(1) and O(n) operations.

Exercise 2: Efficiency

Why is efficiency important in programming?

← Previous Next