Evaluating Algorithm Efficiency

# Evaluating Algorithm Efficiency ## Objectifs et prérequis This chapter aims to equip Lower Sixth students with the analytical tools to evaluate and compare the efficiency of algorithms. Students will learn to quantify time and space requirements using asymptotic notation, classify computational problems by their inherent difficulty, perform dry runs to trace algorithm behavior, and apply optimization techniques. By the end, they will be able to select appropriate algorithms for given problem sizes and justify choices based on complexity analysis. **Prerequisites:** - Proficiency in basic programming constructs (loops, conditionals, functions) in a high-level language (e.g., Python, Java). - Understanding of arrays, lists, and basic data structures (stacks, queues). - Familiarity with mathematical functions (polynomials, logarithms, exponentials) and limits. - Ability to trace simple code segments manually (dry run). --- ## I. Complexity of Algorithms ### Definition and Importance Algorithm complexity measures the computational resources (time and space) required by an algorithm as a function of input size $n$. Time complexity refers to the number of basic operations executed; space complexity refers to the memory used. Analyzing complexity allows prediction of performance scalability and identification of bottlenecks before implementation. > **Key Concept:** Complexity is expressed as a function $T(n)$ or $S(n)$, where $n$ is the size of the input (e.g., number of elements in an array, number of nodes in a graph). We focus on worst-case complexity unless specified otherwise, as it provides a performance guarantee. ### Time vs. Space Complexity - **Time Complexity ($T(n)$):** Counts fundamental operations (comparisons, assignments, arithmetic ops). - **Space Complexity ($S(n)$):** Measures auxiliary space (excluding input storage). - **Trade-off:** Sometimes reducing time increases space (e.g., memoization) and vice versa. ### Step-by-Step Example: Linear Search Consider searching for a key $k$ in an unsorted array $A[0..n-1]$: ```python def linear_search(A, k): for i in range(n): # Loop runs n times in worst case if A[i] == k: # One comparison per iteration return i return -1 ``` - **Worst-case time:** Key not present or at last position → $n$ iterations × 1 comparison = $n$ operations. Thus, $T(n) = n$. - **Best-case time:** Key at first position → 1 comparison → $T(n) = 1$. - **Average-case time:** Assuming uniform distribution → $(n+1)/2$ → still proportional to $n$. - **Space Complexity:** Only uses variables $i$ and $k$ → constant space → $S(n) = 1$. > **Rule:** For a loop that runs $n$ times with constant-time operations inside, time complexity is $O(n)$. ### Exercises d’Application Corrigés **Exercise 1:** Determine the time complexity of finding the maximum element in an array of size $n$. *Solution:* Initialize `max = A[0]`. Loop from $i=1$ to $n-1$: compare $A[i]$ with `max`, update if larger. - Comparisons: $n-1$ - Assignments: up to $n-1$ (worst case if array is strictly increasing) - Total operations: $\approx 2n$ → linear in $n$ **Answer:** $T(n) = O(n)$ **Exercise 2:** What is the space complexity of the linear search algorithm above? *Solution:* Only scalar variables (`i`, `k`, return index) are used. No additional data structures grow with $n$. **Answer:** $S(n) = O(1)$ **Exercise 3:** Analyze the time complexity of nested loops: ```python for i in range(n): for j in range(n): print(i, j) ``` *Solution:* Outer loop runs $n$ times. For each $i$, inner loop runs $n$ times. Total iterations: $n \times n = n^2$. Each iteration does constant work (print). **Answer:** $T(n) = O(n^2)$ --- ## II. Big-O Notation ### Definition and Purpose Big-O notation describes the upper bound of a function’s growth rate. It allows us to compare algorithms by focusing on dominant terms as $n$ grows large, ignoring constants and lower-order terms. > **Formal Definition:** $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq c \cdot g(n)$ for all $n \geq n_0$. > This means $g(n)$ is an asymptotic upper bound on $f(n)$. ### Properties of Big-O 1. **Constant factors are ignored:** $O(5n^2) = O(n^2)$ 2. **Lower-order terms are dropped:** $O(n^2 + 3n + 10) = O(n^2)$ 3. **Transitivity:** If $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$ 4. **Sum rule:** $O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))$ 5. **Product rule:** $O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))$ ### Common Complexity Classes | Class | Notation | Example Algorithms | Growth Rate (Slow to Fast) | |----------------|----------|---------------------------------------------|----------------------------| | Constant | $O(1)$ | Array access, hash table lookup | Slowest | | Logarithmic | $O(\log n)$ | Binary search, heap operations | | | Linear | $O(n)$ | Linear search, traversing a list | | | Linearithmic | $O(n \log n)$ | Merge sort, quicksort (avg), heap sort | | | Quadratic | $O(n^2)$ | Bubble sort, selection sort, nested loops | | | Cubic | $O(n^3)$ | Matrix multiplication (naive), triple nested loops | | | Exponential | $O(2^n)$ | Brute-force subset generation, TSP (naive) | | | Factorial | $O(n!)$ | Brute-force permutation generation | Fastest | > **Rule:** For polynomial functions, Big-O is determined by the highest power of $n$. For logarithmic bases, $O(\log_b n) = O(\log n)$ since $\log_b n = \frac{\log n}{\log b}$ and constants are ignored. ### Step-by-Step Example: Proving $T(n) = 3n^2 + 2n + 1$ is $O(n^2)$ We need constants $c$ and $n_0$ such that $3n^2 + 2n + 1 \leq c \cdot n^2$ for all $n \geq n_0$. - For $n \geq 1$, $2n \leq 2n^2$ and $1 \leq n^2$ (since $n^2 \geq n \geq 1$). - Thus, $3n^2 + 2n + 1 \leq 3n^2 + 2n^2 + n^2 = 6n^2$. - Choose $c = 6$ and $n_0 = 1$. - Check: $3(1)^2 + 2(1) + 1 = 6 \leq 6 \cdot 1^2 = 6$ ✓ **Conclusion:** $3n^2 + 2n + 1 = O(n^2)$ ### Exercises d’Application Corrigés **Exercise 1:** Show that $T(n) = 5n \log n + 7n$ is $O(n \log n)$. *Solution:* - $5n \log n + 7n \leq 5n \log n + 7n \log n$ for $n \geq 2$ (since $\log n \geq 1$ when $n \geq 2$) - $= 12n \log n$ - Choose $c = 12$, $n_0 = 2$ **Answer:** $T(n) = O(n \log n)$ **Exercise 2:** Is $T(n) = 2^n + n^2$ $O(2^n)$? Justify. *Solution:* - For $n \geq 4$, $n^2 \leq 2^n$ (since $2^4=16$, $4^2=16$; and $2^n$ grows faster). - Thus, $2^n + n^2 \leq 2^n + 2^n = 2 \cdot 2^n$ - Choose $c = 2$, $n_0 = 4$ **Answer:** Yes, $T(n) = O(2^n)$ **Exercise 3:** Arrange in increasing growth order: $O(\log n)$, $O(n)$, $O(n \log n)$, $O(1)$, $O(n^2)$ *Solution:* Constants grow slowest → logarithmic → linear → linearithmic → quadratic **Answer:** $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ --- ## III. Computational Problem Types ### Classification by Inherent Difficulty Problems are categorized based on the best-known algorithm’s complexity. This helps determine feasibility for large inputs. > **Key Concept:** A problem is *tractable* if it can be solved in polynomial time ($O(n^k)$ for constant $k$). *Intractable* problems require super-polynomial time (e.g., exponential) and are impractical for large $n$. ### Tractable Problems (P) These admit polynomial-time solutions. - **Sorting:** Merge sort ($O(n \log n)$) - **Searching:** Binary search in sorted array ($O(\log n)$) - **Shortest Path:** Dijkstra’s algorithm ($O((V+E)\log V)$ with heap) - **Minimum Spanning Tree:** Kruskal’s or Prim’s ($O(E \log V)$) ### Intractable Problems No known polynomial-time solution; often NP-hard. - **Traveling Salesperson Problem (TSP):** Find shortest route visiting all cities exactly once. Best exact algorithms: $O(n^2 2^n)$ (dynamic programming) or worse. - **Knapsack Problem:** Maximize value without exceeding weight capacity. Dynamic programming solution: $O(nW)$, where $W$ is capacity — *pseudo-polynomial* (not polynomial in input size, which is $\log W$). - **Boolean Satisfiability (SAT):** Determine if a Boolean formula has a satisfying assignment. NP-complete; best known: $O(1.307^n)$ for 3-SAT, still exponential. > **Rule:** If a problem’s input size is measured in bits (e.g., a number $W$), an algorithm running in $O(W)$ time is *not* polynomial — it’s exponential in the number of bits ($\log W$). ### Step-by-Step Example: Why Knapsack is Not Strongly Polynomial Consider 0/1 Knapsack: - Input: $n$ items with weights $w_i$, values $v_i$, capacity $W$. - DP table size: $n \times (W+1)$ → time $O(nW)$. - But $W$ is a number; its representation in binary uses $\log_2 W$ bits. - If $W = 2^{100}$, then $\log_2 W = 100$ bits, but $W = 2^{100}$ → $nW$ is huge even for small $n$. - Thus, runtime is exponential in the *input size* (number of bits), not polynomial. **Conclusion:** Knapsack is weakly NP-complete; not strongly polynomial. ### Exercises d’Application Corrigés **Exercise 1:** Classify the problem of finding the maximum element in an unsorted array. *Solution:* Requires checking each element at least once → $\Omega(n)$ lower bound. Linear scan achieves $O(n)$. **Answer:** Tractable (linear time) **Exercise 2:** Is determining if a number is prime tractable? *Solution:* The AKS primality test runs in $O(\log^{6} n)$ time — polynomial in the number of bits ($\log n$). **Answer:** Yes, tractable (since 2002) **Exercise 3:** Why is brute-force TSP ($O(n!)$) worse than dynamic programming ($O(n^2 2^n)$)? *Solution:* - For $n=20$: - $n! \approx 2.4 \times 10^{18}$ - $n^2 2^n = 400 \times 1,048,576 \approx 4.2 \times 10^8$ - DP is vastly faster for moderate $n$. **Answer:** $O(n^2 2^n)$ is exponentially better than $O(n!)$ for $n > 10$. --- ## IV. Algorithm Complexity, Dry Runs and Optimisation ### Dry Runs (Trace Tables) A dry run manually executes an algorithm step-by-step, recording variable values at each stage. It verifies correctness and helps derive complexity. > **Rule:** To perform a dry run, create a table with columns for each variable and a row for each iteration or key step. Initialize before the loop, update per step. ### Step-by-Step Example: Dry Run of Binary Search Search for $k=7$ in sorted array $A = [1, 3, 5, 7, 9, 11, 13]$ ($n=7$): ```python low = 0 high = n-1 while low <= high: mid = (low + high) // 2 if A[mid] == k: return mid elif A[mid] < k: low = mid + 1 else: high = mid - 1 return -1 ``` | Step | low | high | mid | A[mid] | Comparison (A[mid] vs k) | Action | |------|-----|------|-----|--------|---------------------------|------------------| | Init | 0 | 6 | - | - | - | Start | | 1 | 0 | 6 | 3 | 7 | 7 == 7 | Return index 3 | **Result:** Found at index 3 in 1 iteration. - Worst case (e.g., $k=2$): - Step 1: mid=3, A[3]=7 > 2 → high=2 - Step 2: low=0, high=2 → mid=1, A[1]=3 > 2 → high=0 - Step 3: low=0, high=0 → mid=0, A[0]=1 < 2 → low=1 - Step 4: low=1 > high=0 → exit → return -1 - 3 iterations → $\lfloor \log_2 7 \rfloor + 1 = 3$ **Conclusion:** Time complexity $O(\log n)$ ### Optimisation Techniques Optimisation reduces complexity by improving algorithm design, not just code tweaks. 1. **Avoid Redundant Computation:** Store intermediate results. - *Example:* In Fibonacci recursion, $fib(n)$ calls $fib(n-1)$ and $fib(n-2)$, leading to $O(2^n)$. Memoization reduces to $O(n)$. 2. **Early Termination:** Exit loops when result is known. - *Example:* Bubble sort can stop if no swaps occur in a pass (best case $O(n)$ for sorted input). 3. **Data Structure Choice:** Use hash tables for $O(1)$ lookups instead of linear search ($O(n)$). 4. **Divide and Conquer:** Break problem into subproblems (e.g., merge sort: $O(n \log n)$ vs. selection sort $O(n^2)$). 5. **Preprocessing:** Sort data once to enable faster queries (e.g., sort then binary search vs. repeated linear search). > **Rule:** Optimisation targets the dominant term in complexity. Reducing constants helps but doesn’t change Big-O class. ### Step-by-Step Example: Optimising Duplicate Check **Naive:** Check all pairs for duplicates in array $A[0..n-1]$: ```python for i in range(n): for j in range(i+1, n): if A[i] == A[j]: return True return False ``` - Comparisons: $\sum_{i=0}^{n-2} (n-1-i) = \frac{n(n-1)}{2} = O(n^2)$ **Optimised:** Use a hash set to track seen elements: ```python seen = set() for x in A: if x in seen: return True seen.add(x) return False ``` - Set operations (add, check) are $O(1)$ average case. - Loop runs $n$ times → $O(n)$ time. - Space: $O(n)$ for the set (trade space for time). **Dry Run for Optimised Version** ($A = [2, 5, 3, 5, 1]$): | Step | x | seen before | x in seen? | Action | seen after | |------|----|-------------|------------|----------------------|------------------| | Init | - | {} | - | Start | {} | | 1 | 2 | {2}? | No | Add 2 | {2} | | 2 | 5 | {2,5}? | No | Add 5 | {2,5} | | 3 | 3 | {2,5,3}? | No | Add 3 | {2,5,3} | | 4 | 5 | {2,5,3,5}? | Yes | Return True | - | **Result:** Duplicate found at step 4. ### Exercises d’Application Corrigés **Exercise 1:** Dry run the following to find if array has zero sum subset (naive): ```python def has_zero_sum(A): n = len(A) for i in range(n): s = 0 for j in range(i, n): s += A[j] if s == 0: return True return False ``` For $A = [1, 2, -3, 4]$ *Solution:* | i | j | s (A[i..j]) | s==0? | |---|---|-------------|-------| | 0 | 0 | 1 | No | | 0 | 1 | 1+2=3 | No | | 0 | 2 | 3+(-3)=0 | Yes → return True | **Answer:** Returns True at i=0, j=2 (subarray [1,2,-3]) **Exercise 2:** Optimise the zero-sum subset check using prefix sums and a hash set. State complexity. *Solution:* - Compute prefix sum $P[0]=0$, $P[i]=A[0]+...+A[i-1]$ - Zero-sum subarray exists iff two prefix sums are equal (or $P[i]=0$) - Algorithm: ```python def has_zero_sum_opt(A): prefix = 0 seen = {0} # P[0] = 0 for x in A: prefix += x if prefix in seen: return True seen.add(prefix) return False ``` - Time: $O(n)$ (one pass, set ops $O(1)$) - Space: $O(n)$ (worst case, all prefix sums distinct) **Answer:** $O(n)$ time, $O(n)$ space **Exercise 3:** Why is optimising a bubble sort to stop early not change its worst-case complexity? *Solution:* - Best case (already sorted): $O(n)$ with early stop. - Worst case (reverse sorted): Still requires $n-1$ passes, each with decreasing comparisons → $\frac{n(n-1)}{2} = O(n^2)$. - Early stop only helps in best/average cases; worst-case input still triggers full work. **Answer:** Worst-case remains $O(n^2)$; optimisation is input-dependent. --- ## V. Integration Activity ### Activity: Comparing Search Algorithms **Scenario:** You are building a contact list app for a school with 10,000 students. You must implement a search feature to find a student by ID (unique integer). **Task:** 1. Implement linear search and binary search (assuming sorted list). 2. Perform dry runs for both to find ID=5000 in a list where IDs are sorted 1 to 10000. 3. Calculate exact number of comparisons for worst case and average case. 4. Discuss space complexity and preprocessing cost. 5. Recommend which to use and justify with complexity analysis. ### Step-by-Step Solution #### 1. Algorithms **Linear Search:** ```python def linear_search(ids, target): for i in range(len(ids)): if ids[i] == target: return i return -1 ``` **Binary Search:** (requires sorted list) ```python def binary_search(ids, target): low, high = 0, len(ids)-1 while low <= high: mid = (low + high) // 2 if ids[mid] == target: return mid elif ids[mid] < target: low = mid + 1 else: high = mid - 1 return -1 ``` #### 2. Dry Runs for target=5000, ids=[1,2,3,...,10000] **Linear Search:** - Checks each element from index 0 upward. - Target at index 4999 (since IDs start at 1: ID=1 at idx0, ID=5000 at idx4999). - Comparisons: 5000 (checks IDs 1 through 5000) **Binary Search:** | Step | low | high | mid | ids[mid] | Comparison | Action | |------|-----|------|-----|----------|-------------------------|----------------| | Init | 0 | 9999 | - | - | - | Start | | 1 | 0 | 9999 | 4999| 5000 | 5000 == 5000 → found | Return 4999 | **Result:** Found in 1 comparison (best case for this target). *Note:* For binary search, we analyze worst case (target not present or at ends). #### 3. Comparison Counts | Metric | Linear Search | Binary Search | |-----------------------|---------------------|------------------------| | **Worst Case** | $n$ comparisons | $\lfloor \log_2 n \rfloor + 1$ comparisons | | For $n=10000$ | 10,000 | $\lfloor \log_2 10000 \rfloor + 1 = 13 + 1 = 14$ | | **Average Case** | $(n+1)/2$ | $\approx \log_2 n$ | | For $n=10000$ | 5000.5 | ~13.3 | | **Best Case** | 1 | 1 | #### 4. Space and Preprocessing - **Linear Search:** - Space: $O(1)$ (only loop index and target) - Preprocessing: None (works on unsorted list) - **Binary Search:** - Space: $O(1)$ (same variables) - Preprocessing: Requires sorted list. Sorting 10,000 elements: - Efficient sort (merge/quick): $O(n \log n) \approx 10000 \times 13 = 130,000$ operations - One-time cost; amortized over many searches #### 5. Recommendation - If **only one search** is needed: Linear search is better (no sorting overhead: 10,000 vs 130,000+ operations). - If **multiple searches** are expected (e.g., >13 searches): Binary search wins after preprocessing. - Break-even: Let $k$ = number of searches. - Linear total: $k \times 10000$ - Binary total: $130000 + k \times 14$ - Solve: $10000k = 130000 + 14k$ → $9986k = 130000$ → $k \approx 13.02$ - After 14 searches, binary search is more efficient. - **Verdict:** For a contact list app with repeated searches (user looks up multiple contacts), **binary search after sorting** is strongly preferred. Preprocessing cost is amortized, and each search is vastly faster ($O(\log n)$ vs $O(n)$). > **Key Insight:** Always consider the *usage pattern*. Optimisation depends on frequency of operations. ### Exercises d’Application Corrigés (Integration) **Exercise 1:** For $n=1,000,000$, how many more comparisons does linear search make than binary search in the worst case? *Solution:* - Linear: $n = 1,000,000$ - Binary: $\lfloor \log_2 1000000 \rfloor + 1$ - $2^{19} = 524,288$; $2^{20} = 1,048,576$ → $\log_2 1000000 \approx 19.93$ → floor=19 → +1 = 20 - Difference: $1,000,000 - 20 = 999,980$ **Answer:** 999,980 more comparisons **Exercise 2:** If sorting takes $O(n \log n)$ and each binary search is $O(\log n)$, how many searches $k$ make binary search better than linear search for large $n$? *Solution:* - Linear total for $k$ searches: $k \cdot O(n) = O(kn)$ - Binary total: $O(n \log n) + k \cdot O(\log n) = O(n \log n + k \log n)$ - Set $kn > n \log n + k \log n$ for large $n$ - Divide by $n$ (assuming $n>0$): $k > \log n + \frac{k \log n}{n}$ - For large $n$, $\frac{k \log n}{n} \approx 0$ → $k > \log n$ **Answer:** When number of searches $k > \log n$, binary search with preprocessing is better. **Exercise 3:** Why might you still choose linear search over binary search even for large $n$ in some real-time systems? *Solution:* - Binary search requires the list to be sorted and *remain sorted*. - If the list undergoes frequent insertions/deletions, maintaining sort order costs $O(n)$ per operation (e.g., shifting in array). - Linear search on unsorted list has $O(1)$ insert/delete (append) and $O(n)$ search. - If updates are frequent and searches rare, linear search avoids sorting overhead. **Answer:** In dynamic datasets with high update frequency, linear search may be preferable despite worse search complexity. --- ## Synthèse du chapitre - **Complexity Analysis:** Quantifies time/space as functions of input size $n$, focusing on worst-case for guarantees. - **Big-O Notation:** Provides asymptotic upper bound; ignores constants and lower-order terms; governed by rules (sum, product, transitivity). - **Problem Classification:** Tractable problems have polynomial-time solutions ($P$); intractable problems (e.g., TSP, SAT) require super-polynomial time and are often NP-hard. - **Dry Runs:** Essential for tracing algorithm behavior, verifying correctness, and deriving operation counts. - **Optimisation:** Improves complexity via algorithmic choices (e.g., hash sets, divide-and-conquer), not just code tweaks; involves time-space trade-offs. - **Integration:** Real-world decisions depend on input size, operation frequency (searches vs. updates), and preprocessing costs; asymptotic analysis guides but does not replace context-aware judgment. --- ## Glossaire - **Time Complexity:** The number of basic operations an algorithm executes as a function of input size $n$, typically expressed in Big-O notation. - **Space Complexity:** The amount of memory an algorithm uses beyond the input, as a function of $n$. - **Big-O Notation ($O$):** A mathematical notation describing the upper bound of a function’s growth rate; $f(n) = O(g(n))$ means $f(n)$ grows no faster than $g(n)$ asymptotically. - **Worst-Case Complexity:** The maximum time or space required by an algorithm over all inputs of size $n$. - **Tractable Problem:** A problem solvable in polynomial time ($O(n^k)$ for constant $k$); considered efficiently solvable. - **Intractable Problem:** A problem for which no known polynomial-time algorithm exists; often requires exponential or factorial time. - **Dry Run:** A manual step-by-step execution of an algorithm, recording variable values to trace logic and compute operation counts. - **Optimisation:** The process of improving an algorithm’s efficiency (time or space) through better design, data structures, or early termination. - **Preprocessing:** An initial step (e.g., sorting) performed once to enable faster subsequent operations, trading upfront cost for long-term gain. - **Amortized Cost:** The average cost per operation over a sequence of operations, useful when occasional expensive steps are offset by many cheap ones. - **NP-Hard:** A class of problems at least as hard as the hardest problems in NP; solving one in polynomial time would imply $P = NP$. - **Polynomial Time:** An algorithm runs in polynomial time if its complexity is $O(n^k)$ for some constant $k$; the benchmark for tractability. ---