Algorithm Efficiency Comparison

Discrete Math · Axiom Academy

REAL WORLD Algorithm Efficiency: Database Query Strategies Discover why Big-O notation matters by comparing two database join algorithms on real data—where O(n²) grinds to a halt while O(n) stays lightning fast. Imagine you're building an e-commerce platform. You have two database tables: Orders and Customers . To generate a sales report, you need to match each order with its customer information. Your database system has two options for performing this join operation. Let's explore both approaches and see how their algorithmic efficiency affects performance on real data. How it works: For each order, scan through ALL customers to find a match. How it works: Build a hash table of customers, then look up each order's match instantly. Based on the time complexities, what do you think will happen when we run these algorithms on 1 million orders and 100,000 customers? Let's visualize the actual execution time for both algorithms. Use the slider to see how performance changes with data size. Here's a detailed view of how execution time grows with data size for both algorithms: 1,000,000 × 100,000 = 100 billion comparisons Every order must check against EVERY customer. This quadratic growth means that doubling the data quadruples the work. 100,000 + 1,000,000 = 1.1 million operations Build hash table once (100K), then do one lookup per order (1M). Linear growth means doubling the data only doubles the work.

This is the written version of the interactive lesson above. See the full Discrete Math course.