Time Complexity: Analysis, Big-O, and Algorithm Efficiency

TAKEAWAYS:

• Time complexity describes how runtime grows with input size, using Big-O notation (e.g., O(n²) for nested loops).
• Asymptotic analysis ignores constants and focuses on dominant terms (e.g., O(2n + 10) simplifies to O(n)).
• Common complexities (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)) determine algorithm scalability.
• Real-world systems (e.g., Daraz’s order queue, Ncell’s call routing) use complexity to optimize performance.
• Amortized analysis explains why some operations (e.g., dynamic arrays) appear slow but average out efficiently.
• Always analyze worst-case scenarios unless the problem guarantees constraints (e.g., sorted input for binary search).

1. Why Measure Time Complexity?

Algorithms solve problems, but their efficiency varies. For example:

• Linear search checks each element one by one → O(n) time.
• Binary search halves the search space → O(log n) time.

Real-world analogy:

• Ncell’s call routing: Uses a hash table (O(1) lookup) to connect calls instantly. If it used linear search (O(n)), delays would cripple the network during peak hours.

2. Big-O Notation: The Language of Efficiency

Big-O describes the upper bound of an algorithm’s growth rate. It answers: "How does runtime scale as input size (n) grows?"

Key Rules for Big-O

1. Drop constants: O(2n) → O(n). Constants don’t matter for large n.
2. Keep the dominant term: O(n² + n) → O(n²).
3. Ignore lower-order terms: O(n³ + 1000) → O(n³).

Example:

def sum_array(arr):
    total = 0
    for num in arr:       # O(n)
        total += num
    for num in arr:       # O(n)
        total += num
    return total           # O(1)

Time Complexity: O(n) + O(n) = O(2n) → O(n) (simplified).

Trace Table:

3. Common Time Complexities

Visual Growth:

4. Best-Case, Average-Case, and Worst-Case Analysis

Why worst-case matters:

• Khalti’s payment system must handle worst-case scenarios (e.g., all transactions failing) to avoid crashes during Dashain sales.

5. Amortized Analysis: The Hidden Costs

Some operations appear expensive but average out over time. Example:

• Dynamic arrays (e.g., Python lists):
  • Appending is O(1) amortized because occasional resizing (O(n)) is spread across many O(1) operations.

Trace of Array Resizing:

sequenceDiagram
  participant Array as Dynamic Array
  participant User as User
  User->>Array: Append (100 times)
  loop First 99 appends
    Array->>User: O(1) time
  end
  Array->>Array: Resize (O(n))
  User->>Array: 100th append (O(1))
  note right of Array: Resize happens every 2x capacity
  note right of Array: Amortized O(1) per append

Real-world tie-in:

• WhatsApp’s message queue: Uses amortized analysis to handle sudden spikes in messages (e.g., during a football match).

6. Space Complexity

Just as time complexity measures runtime, space complexity measures memory usage. Notations:

• O(1): Constant space (e.g., swapping two variables).
• O(n): Linear space (e.g., storing an array of size n).
• O(n²): Quadratic space (e.g., a 2D matrix).

Example: Fibonacci

# O(n) space (stores all fib numbers)
def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# O(1) space (iterative)
def fib_iterative(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

7. Comparing Algorithms: Trade-offs

Real-world trade-off:

• Google Maps’ routing:
  • Uses Dijkstra’s algorithm (O(n²) with adjacency matrix) for small cities.
  • Switches to A search (O(n log n))* for larger cities to balance speed and memory.

8. Practical Examples from Nepal

1. eSewa’s Payment Processing:
   • Uses hash tables (O(1) lookup) to verify user transactions.
   • Without hashing, verifying 1 million transactions would take O(n) time → delays during festivals.

2. NTC’s Internet Routing:

   • Employs priority queues (O(log n) insertion) to manage network traffic during peak hours (e.g., 12 AM).
   • Without prioritization, lower-priority data (e.g., emails) would get stuck behind streaming.

3. Daraz’s Order Fulfillment:

   • First-In-First-Out (FIFO) queue (O(1) per operation) ensures orders are processed in arrival order.
   • If Daraz used a stack (LIFO), the last order placed would be fulfilled first—causing customer complaints.

Exam Tip

1. Always simplify Big-O correctly:

   • ❌ O(n² + n log n) → ❌ O(n² log n) (wrong!)
   • ✅ O(n² + n log n) → ✅ O(n²) (correct, since n² dominates).

2. Memorize these pairs:

   • Binary search: O(log n)
   • Linear search: O(n)
   • Bubble sort: O(n²)
   • Merge sort: O(n log n)

3. Watch for hidden complexities:

   • A nested loop with i and j → O(n²).
   • A loop inside a loop with i and j where j depends on i → O(n³).

4. Real-world questions are common:

   • "Why does Pathao’s driver assignment use a priority queue instead of a stack?" Answer: Priority queues (O(log n)) ensure the nearest available driver is assigned first, reducing wait times.

5. Practice tracing:

   • For any algorithm, draw a table showing variable changes at each step (like the sum_array trace above).

Final Visual Summary: