Understanding Big O Complexity in an E-Commerce Application

Big O notation helps us analyze how an algorithm's runtime grows as the input size increases. In an e-commerce application, different tasks—like searching for products, sorting items, and checking user sessions—have different time complexities. Writing efficient code ensures that your application scales well as the number of users and products grows.

This post will analyze real-world e-commerce operations, explaining their Big O complexity and implementing them in pure TypeScript (with pseudocode where database interactions are involved).

O(1) - Constant Time Complexity

Example: Checking if a user is logged in

Operations that run in O(1) (constant time) do not depend on the size of the input. No matter how many users the system has, checking whether a user is logged in takes the same amount of time.

Code Example (TypeScript)

1function isLoggedIn(userId: string): boolean {
2    return sessionStore.has(userId);
3}
4

Explanation

• sessionStore.has(userId) performs a direct lookup in a hash table or set, which is a constant-time operation.
• Whether there are 10 users or 1 million users, the lookup takes the same amount of time.

When to Optimize?

• Not necessary—this is already the most efficient approach.

O(log n) - Logarithmic Time Complexity

Example: Finding a product by ID in a sorted list (Binary Search)

Operations with O(log n) (logarithmic time complexity) scale very efficiently because they divide the problem in half with each step. Searching for a product in a sorted list using binary search is a common example.

Code Example (TypeScript)

1function findProductById(products: Product[], id: string): Product | null {
2    let left = 0, right = products.length - 1;
3
4    while (left <= right) {
5        let mid = Math.floor((left + right) / 2);
6        if (products[mid].id === id) return products[mid];
7        if (products[mid].id < id) left = mid + 1;
8        else right = mid - 1;
9    }
10
11    return null;
12}
13

Explanation

• This function reduces the search space by half in each iteration.
• Instead of checking each product one by one (which would be O(n)), binary search only requires log₂(n) operations.

Performance Comparison

If we have 1,000,000 products:

• Linear search (O(n)): Worst case = 1,000,000 checks.
• Binary search (O(log n)): Worst case = log₂(1,000,000) ≈ 20 checks. 🚀

When to Optimize?

• If you’re searching for products frequently, using binary search is much better than linear search.
• If the dataset is unsorted, consider hash tables (Map in TypeScript) for O(1) lookups.

O(n) - Linear Time Complexity

Example: Filtering products by category

Operations with O(n) (linear time complexity) scale proportionally with input size. If we filter products based on category, the function must check each product individually, leading to O(n) complexity.

Code Example (TypeScript)

1function filterByCategory(products: Product[], category: string): Product[] {
2    return products.filter(p => p.category === category);
3}
4

Explanation

• The .filter() method iterates through every product.
• If the dataset doubles in size, the function will take twice as long.

When to Optimize?

• If filtering is frequent, use indexes in the database for faster queries instead of filtering in TypeScript.

O(n log n) - Quasilinear Time Complexity

Example: Sorting products by price

Sorting is more complex than searching or filtering. Most efficient sorting algorithms (like Merge Sort or QuickSort) run in O(n log n) time.

Code Example (TypeScript)

1function sortByPrice(products: Product[]): Product[] {
2    return products.sort((a, b) => a.price - b.price);
3}
4

Explanation

• Sorting requires comparing elements and rearranging them.
• The JavaScript .sort() method in V8 uses Timsort, which has an average complexity of O(n log n).

Performance Comparison

For 1,000,000 products:

• Bubble Sort (O(n²)) → Worst case 1,000,000,000,000 comparisons ❌
• Merge Sort (O(n log n)) → Worst case ~20,000,000 comparisons ✅

When to Optimize?

• If sorting is frequent, store pre-sorted lists or use indexing in the database.

O(n²) - Quadratic Time Complexity

Example: Finding duplicate orders in a list

Quadratic operations occur when we compare each element with every other element, leading to nested loops.

Code Example (TypeScript)

1function findDuplicateOrders(orders: Order[]): Order[] {
2    let duplicates: Order[] = [];
3
4    for (let i = 0; i < orders.length; i++) {
5        for (let j = i + 1; j < orders.length; j++) {
6            if (orders[i].id === orders[j].id) {
7                duplicates.push(orders[i]);
8            }
9        }
10    }
11
12    return duplicates;
13}
14

Explanation

• The outer loop iterates over each order.
• The inner loop compares that order with every other order.
• If there are 10,000 orders, this results in 100,000,000 comparisons ❗

How to Optimize?

Instead of nested loops, use a hash table (Map in TypeScript) for an O(n) solution:

1function findDuplicateOrdersOptimized(orders: Order[]): Order[] {
2    let seen = new Map<string, Order>();
3    let duplicates: Order[] = [];
4
5    for (let order of orders) {
6        if (seen.has(order.id)) duplicates.push(order);
7        else seen.set(order.id, order);
8    }
9
10    return duplicates;
11}
12

✅ Now it runs in O(n) instead of O(n²)!

Conclusion

Understanding Big O complexity is critical for designing efficient applications. In this guide, we analyzed real-world e-commerce tasks, from O(1) (constant lookups) to O(n²) (nested loops).

Key Takeaways:

✔ Optimize common tasks like search, filtering, and sorting.
✔ Use hash tables (Map) to avoid O(n²) loops.
✔ If a task runs too slow, check if a better algorithm exists.