Time & Space Complexity: Big-O, Ω, Θ, and Analysis

TAKEAWAYS:

• Time complexity describes how runtime grows with input size, while space complexity measures memory usage.
• Big-O notation (O) gives the upper bound of growth, Ω (omega) gives the lower bound, and Θ (theta) gives tight bounds.
• Common complexities include O(1), O(log n), O(n), O(n log n), and O(n²), each representing different algorithmic behaviors.
• Analyzing complexity helps choose the right algorithm for large datasets (e.g., sorting 1M records vs. 100).
• Real-world examples include Daraz’s order processing (queue complexity) and Ncell’s call routing (hash table collisions).
• Always justify your answer with examples and trace tables for full marks in exams.

1. Introduction to Complexity Analysis

Algorithms solve problems, but their efficiency depends on input size (n) and resources used. We analyze two key metrics:

• Time Complexity: How runtime scales with input size (e.g., sorting 100 vs. 1M items).
• Space Complexity: How memory usage scales (e.g., storing 100 vs. 100K elements).

1.1 Why Analyze Complexity?

• Performance Prediction: Estimate runtime for large inputs (e.g., NEPSE stock data).
• Algorithm Selection: Choose between O(n²) bubble sort and O(n log n) merge sort for 10,000 records.
• Resource Optimization: Avoid memory leaks in apps like eSewa’s transaction logs.

1.2 Growth Rates of Common Complexities

flowchart TD
  A["O(1)"] --> B["Constant"]
  B --> C["O(log n)"]
  C --> D["Logarithmic"]
  D --> E["O(n)"]
  E --> F["Linear"]
  F --> G["O(n log n)"]
  G --> H["Linearithmic"]
  H --> I["O(n²)"]
  I --> J["Quadratic"]
  J --> K["O(2ⁿ)"]
  K --> L["Exponential"]
  L --> M["O(n!)"]
  M["Factorial"]

Key Insight: O(n²) grows much faster than O(n log n) for large n.

2. Time Complexity Notations

2.1 Big-O (O): Upper Bound

• Describes the worst-case runtime.
• Example: Merge sort is O(n log n) because it divides the array into halves (log n steps) and merges them (n steps).

2.2 Omega (Ω): Lower Bound

• Describes the best-case runtime.
• Example: Binary search is Ω(log n) because it always halves the search space.

2.3 Theta (Θ): Tight Bound

• Describes the average-case runtime (both upper and lower bounds match).
• Example: Insertion sort is Θ(n²) in the worst and average cases.

2.4 Comparison Table

3. How to Determine Complexity?

3.1 Count Basic Operations

• Focus on loops and nested loops (e.g., for inside for).
• Ignore constants and lower-order terms (e.g., O(2n + 5) → O(n)).

3.2 Worked Example: Linear Search

Algorithm:

def linear_search(arr, target):
    for i in range(len(arr)):  # O(n) loop
        if arr[i] == target:
            return i
    return -1

Trace Table:

Complexity: O(n) (worst case: checks all n elements).

3.3 Worked Example: Binary Search

Algorithm:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:  # O(log n) loop
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Trace Table (for arr = [2, 5, 8, 12, 15], target = 8):

Complexity: O(log n) (halves the search space each time).

4. Space Complexity

Measures auxiliary space (extra memory used beyond input).

• O(1): Constant space (e.g., swapping two variables).
• O(n): Linear space (e.g., storing a copy of the array in merge sort).

Example: Merge Sort Space Usage

Space Complexity: O(n) (requires temporary storage).

5. Real-World Applications

5.1 Daraz’s Order Processing (Queue Complexity)

• Idea: Orders arrive in a FIFO (First-In-First-Out) queue.
• Complexity: Enqueue/dequeue operations are O(1) (efficient for 10,000+ orders/day).
• Why it matters: Delays in processing (e.g., O(n²) sorting) would slow down deliveries.

5.2 Ncell’s Call Routing (Hash Table Collisions)

• Idea: Phone numbers are hashed to route calls quickly.
• Complexity: Average case O(1) (hash table lookup), but collisions degrade to O(n).
• Why it matters: Poor hashing (e.g., linear probing) causes delays during peak hours.

5.3 NEPSE Stock Trading (Sorting Complexity)

• Idea: Sorting daily stock prices for analysis.
• Algorithm Choice:
  • O(n log n): Merge sort (stable, efficient for 100K+ records).
  • Avoid: Bubble sort (O(n²)) for large datasets.

6. Exam Tips

1. Always justify with examples:

   • "Merge sort is O(n log n) because..." (explain divide-and-conquer).
   • "Binary search is O(log n) because..." (halving the search space).

2. Compare algorithms:

   • "Bubble sort is O(n²), while quicksort is O(n log n) on average."

3. Trace tables for clarity:

   • Show step-by-step execution (e.g., binary search trace).

4. Mention real-world impact:

   • "In eSewa, O(1) transaction lookups are critical for speed."

5. Avoid common mistakes:

   • Don’t confuse Ω (lower bound) with O (upper bound).
   • Ignore constants (e.g., O(2n) → O(n)).

6.1 Past Exam Question Practice

Question: Explain merge sort along with its time complexity. Sort the array: [25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11].

Answer: Merge sort uses a divide-and-conquer approach:

1. Divide: Split the array into halves recursively.
2. Conquer: Sort each half.
3. Merge: Combine sorted halves.

Time Complexity: O(n log n) (always, even for worst case).

Step-by-Step Merge Sort:

flowchart TD
  A["Original Array: [25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11]"] --> B["Split into subarrays"]
  B --> C["Left: [25, 37, 48, 25, 23]"]
  B --> D["Right: [17, 31, 45, 7, 21, 15, 8, 11]"]
  C --> E["Split further until single elements"]
  E --> F["Left sub-subarrays: [25], [37], [48], [25], [23]"]
  D --> G["Merge sorted subarrays"]
  G --> H["Left merged: [23, 25, 25, 37, 48]"]
  G --> I["Right merged: [7, 8, 11, 15, 17, 21, 31, 45]"]
  H --> J["Final Sorted Array: [7, 8, 11, 15, 17, 21, 23, 25, 25, 31, 37, 45, 48]"]

Trace of Merging Two Sorted Arrays:

left = [7, 8, 11, 15]
right = [17, 21, 23, 25, 25, 31, 37, 45, 48]
merged = []
i = j = 0
while i < len(left) and j < len(right):
    if left[i] < right[j]:
        merged.append(left[i])
        i += 1
    else:
        merged.append(right[j])
        j += 1
# Append remaining elements
merged.extend(left[i:])
merged.extend(right[j:])

Output: [7, 8, 11, 15, 17, 21, 23, 25, 25, 31, 37, 45, 48]

6.2 Common Pitfalls

• Ignoring worst-case: Always state the worst-case complexity (e.g., quicksort is O(n²) in worst case).
• Confusing Ω and O: Ω is the best case; O is the worst case.
• Forgetting space complexity: Some algorithms (e.g., merge sort) use O(n) extra space.

7. Summary Table of Key Concepts

8. Final Exam Tip

• For numerical questions (e.g., sorting arrays), show the trace of your algorithm.
• For theoretical questions, compare notations (O, Ω, Θ) with real-world examples.
• Always relate to Nepalese context: Mention how Ncell’s call routing or Daraz’s order processing uses these concepts.