Design and Analysis of Algorithms PCCST502 Semester 5 KTU CS 2024 Scheme - Dr Binu V P

  Comparing Growth Rates Using Limits One standard method to compare function sizes is to evaluate: lim ⁡ n → ∞ f ( n ) g ( n )​ The value of this limit determines the relative growth of the functions. Case 1: Limit Equals Zero If: lim ⁡ n → ∞ f ( n ) g ( n ) = 0 \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 then: f ( n ) f(n)  grows slower than g ( n ) g(n) f ( n ) = o ( g ( n ) ) f(n)=o(g(n)) Example Compare: f ( n ) = n f(n)=n and g ( n ) = n 2 g(n)=n^2 Compute: lim ⁡ n → ∞ n n 2 = lim ⁡ n → ∞ 1 n = 0 \lim_{n\to\infty}\frac{n}{n^2}=\lim_{n\to\infty}\frac{1}{n}=0 Hence: n = o ( n 2 ) n=o(n^2) So n 2 n^2  is asymptotically larger. Case 2: Limit Equals a Positive Constant If: lim ⁡ n → ∞ f ( n ) g ( n ) = c , 0 < c < ∞ \lim_{n\to\infty}\frac{f(n)}{g(n)}=c,\quad 0<c<\infty then: Both functions grow at the same rate f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) Example Compare: f ( n ) = 3 n 2 + 2 n f(n)=3n^2+2n and g ( n ) = n 2 g(n)=n^...

  Asymptotic Analysis and Asymptotic Notations Asymptotic analysis is one of the most important concepts in Algorithm Analysis and algorithm design. It provides a mathematical framework for evaluating the efficiency of algorithms as the input size becomes very large. 1. Introduction to Asymptotic Analysis What is Asymptotic Analysis? Asymptotic analysis studies the behavior of algorithms as the input size n n  approaches infinity. Instead of measuring: Actual execution time CPU speed Hardware performance asymptotic analysis focuses on: Growth rate of running time Growth rate of memory usage Why Asymptotic Analysis? Actual running time depends on: Processor speed Compiler optimization Programming language System architecture Therefore, direct timing comparisons are unreliable. Asymptotic analysis provides: Machine-independent evaluation Mathematical comparison of algorithms Scalability prediction Fundamental Idea Suppose two alg...