# Unit 1: Algorithm Analysis (CA324) ## Asymptotic Notations and Growth of Functions An **algorithm** is a finite sequence of well-defined steps that solves a problem. **Asymptotic analysis** studies how running time or space grows as input size $n \to \infty$, ignoring constants and lower-order terms. | Notation | Meaning | Definition | |---|---|---| | **Big-O** $O(g(n))$ | Upper bound | $f(n) \le c\,g(n)$ for all $n \ge n_0$ | | **Omega** $\Omega(g(n))$ | Lower bound | $f(n) \ge c\,g(n)$ for all $n \ge n_0$ | | **Theta** $\Theta(g(n))$ | Tight bound | $c_1 g(n) \le f(n) \le c_2 g(n)$ | | **Little-o** $o(g(n))$ | Strict upper bound | $f(n) < c\,g(n)$ for every $c>0$ | | **Little-omega** $\omega(g(n))$ | Strict lower bound | $f(n) > c\,g(n)$ for every $c>0$ | - Example: $3n^2 + 5n + 2 = \Theta(n^2)$ (choose $c_1=3$, $c_2=4$, $n_0=6$). - Properties: reflexive, transitive; $f=\Theta(g)$ iff $f=O(g)$ and $f=\Omega(g)$; symmetric for Theta only. **Order of growth (slowest to fastest):** $1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < 2^n < n! < n^n$ - Polynomials grow slower than exponentials: $n^k = o(2^n)$ for any constant $k$. - Logarithms grow slower than any positive power of $n$: $\log n = o(n^{\epsilon})$. - Base of logarithm changes only a constant factor: $\log_a n = \log_b n / \log_b a$. ## Complexity of Algorithms - **Time complexity**: number of basic operations as a function of input size $n$. - **Space complexity**: total memory (input + auxiliary + stack) used. Space = fixed part + variable part $S(P) = c + S_p(n)$. - **Best case**: minimum time over inputs of size $n$ (e.g., linear search finds key at index 0, $O(1)$). - **Worst case**: maximum time (linear search key absent, $O(n)$); gives a guaranteed upper bound and is most commonly used. - **Average case**: expected time over a probability distribution of inputs (linear search $\approx (n+1)/2$ comparisons). | Algorithm | Best | Average | Worst | |---|---|---|---| | Linear search | $O(1)$ | $O(n)$ | $O(n)$ | | Binary search | $O(1)$ | $O(\log n)$ | $O(\log n)$ | | Insertion sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | | Quick sort | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | **Steps to analyse:** count loop iterations, add sequential blocks, multiply nested loops, take the dominant term. ## Recurrences A **recurrence** expresses $T(n)$ in terms of $T$ on smaller inputs, e.g., merge sort $T(n) = 2T(n/2) + n$. ### 1. Substitution Method 1. **Guess** the form of the solution. 2. Use **mathematical induction** to prove it and find constants. - Example: $T(n) = 2T(n/2) + n$. Guess $T(n) \le c\,n\log n$. Then $T(n) \le 2c(n/2)\log(n/2) + n = cn\log n - cn + n \le cn\log n$ for $c \ge 1$. ### 2. Recursion Tree Method - Draw the tree of recursive calls, write the cost at each node, sum cost per level, then sum over all levels. - Example: $T(n) = 2T(n/2) + n$ gives $n$ per level over $\log n$ levels, so $T(n) = \Theta(n\log n)$. - Tree is often used to generate a guess that is verified by substitution. ### 3. Master's Theorem For $T(n) = aT(n/b) + f(n)$ with $a \ge 1$, $b > 1$, compare $f(n)$ with $n^{\log_b a}$: - **Case 1**: $f(n) = O(n^{\log_b a - \epsilon})$ implies $T(n) = \Theta(n^{\log_b a})$. - **Case 2**: $f(n) = \Theta(n^{\log_b a})$ implies $T(n) = \Theta(n^{\log_b a}\log n)$. - **Case 3**: $f(n) = \Omega(n^{\log_b a + \epsilon})$ and regularity condition $af(n/b) \le cf(n)$, $c<1$, implies $T(n) = \Theta(f(n))$. Examples: - $T(n)=4T(n/2)+n$: $n^{2}$ dominates, Case 1, $\Theta(n^2)$. - $T(n)=2T(n/2)+n$: Case 2, $\Theta(n\log n)$. - $T(n)=T(n/2)+1$: Case 2, $\Theta(\log n)$ (binary search). - $T(n)=2T(n/2)+n^2$: Case 3, $\Theta(n^2)$. **[Figure: Recursion tree for T(n)=2T(n/2)+n]** A binary tree with root cost n, next level two nodes of n/2 each, and so on, each level summing to n. ## Likely Exam Questions 1. Define Big-O, Omega and Theta notations with examples. (2 marks each) 2. Differentiate best, average and worst case analysis using linear search. 3. Arrange in increasing order of growth: $n\log n$, $2^n$, $n^2$, $\log n$, $n!$. 4. Solve $T(n) = 3T(n/4) + n\log n$ using the Master theorem. 5. Solve $T(n) = 2T(n/2) + n$ using the recursion tree method and verify by substitution. 6. State the Master's theorem and explain its three cases with one example each.