Asymptotic_Notations_v2_1709293258280.pptx

good

1. Asymptotic Notations Big-Oh, Big-Omega and Big-Theta

2. Order of growth Order of growth of a function says how the function grows with increase in values of n.

3. Asymptotic Notations Asymptotic notations are mathematical tools used in computer science and mathematics to analyze and describe the behavior of functions, especially in the context of algorithmic complexity analysis. Different asymptotic notations are available to provide different levels of information and precision when describing how the running time or space complexity of an algorithm grows as the input size increases

4. Most commonly used Asymptotic Notations Big-Oh Notation (O) Big-Omega Notation ( Ω) Big Theta Notation ( Θ) Little O Notation (o) Little Omega Notation ( ω)

5. Step Count Method Vs basic Operation Method vs Asymptotic Notations The step count method focuses on counting the actual individual primitive operations (e.g., arithmetic operations, comparisons, assignments) that an algorithm performs as a function of the input size. The basic operation method abstracts away low-level details and focuses on the algorithm's overall behavior . It expresses the algorithm's runtime in terms of an abstract notion of "basic operations" that represent the dominant factors affecting the time complexity. Asymptotic notation abstracts further from the basic operation method, providing a high-level view of an algorithm's time complexity. It describes how the runtime grows relative to the input size as it approaches infinity

6. Asymptotic order of growth It is used to compare and rank the order of growth. A way of comparing functions that ignores constant factors and small input sizes. Three notations are: Big-Oh, O( g ( n )) : class of functions t ( n ) that grow no faster than g ( n ) Big-Omega, Ω ( g ( n )) : class of functions t ( n ) that grow at least as fast as g ( n ) Big-Theta, Θ ( g ( n )) : class of functions t ( n ) that grow at same rate as g ( n )

7. Formal definition - O -notation A function t(n) is said to be in O(g(n)) , denoted t(n)∈ O(g(n)) , if t(n) is bounded above by some constant multiple of g(n) for all large n , i.e., if there exist some positive constant c and some nonnegative integer n0 such that t(n) ≤ cg(n) for all n ≥ n0 . t ( n ) ≤ c g ( n ) for every n ≥ n

8. Big-oh

9. Formal definition -  -notation A function t(n) is said to be in  (g(n)), denoted t(n)   (g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n , i.e., if there exist some positive constant c and some nonnegative integer n such that t(n)  cg(n) for all n  n

10. Big-omega

11. Formal definition - -notation A function t(n) is said to be in  (g(n)), denoted t(n)   (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n , i.e., if there exist some positive constant c 1 and c 2 and some nonnegative integer n such that c 2 g(n)  t(n)  c 1 g(n) for all n  n

12. Big-theta

13. Summary Big O Notation (O) :It provides an upper bound on the growth rate of a function. It is used to describe the worst-case scenario in terms of time or space complexity. Big Omega Notation (Ω): It provides a lower bound on the growth rate of a function. It describes the best-case scenario in terms of time or space complexity. Big Theta Notation (Θ): It provides both upper and lower bounds on the growth rate of a function. It describes the tight bound on the complexity.

14. Examples Find the odd man out: t(n) = n, g(n) =n 3 t(n) belongs to Big Oh(g(n)) t(n) belongs to Big Omega(g(n)) t(n) belongs to Big Theta(g(n)) Find the relation: T(n)=100n+5, g(n)=n 2 T(n)=1000n 2 , g(n)= logn T(n)=n 3 , g(n)=n 3 T(n)=100n+5, g(n)=n+1

15. Examples Find the odd man out: t(n) = n, g(n) =n 3 t(n) belongs to Big Oh(g(n)) t(n) belongs to Big Omega(g(n)) t(n) belongs to Big Theta(g(n)) Find the relation: T(n)=100n+5, g(n)=n 2 Big Oh T(n)=1000n 2 , g(n)= logn Big Omega T(n)=n 3 , g(n)=n 3 Big Theta T(n)=100n+5, g(n)=n+1 Big Theta

16. Big-oh Examples 100 n +5 ∈ O( n 2 ) 5 n +20 is in O( n ) C= 105; n0 = 1 5n+20 ≤ 5n + 20n (for all n ≥ 1) = 25n. C= 25; n0 = 1

17. Big-omega Examples n 3   ( n 2 ) 10 n 2   ( n 2 ) 0.3 n 2 - 2n   ( n 2 ) 10 n 2 ≥ n 2 for all n ≥ 0. c = 1 and n0 = 0. 0.3 n 2 - 2n ≥ n 2 for all n ≥ 0. c = 1 and n0 = 0.

18. Big-theta Examples (1/2)n(n-1)   ( n 2 ) 0.3 n 2 - 2n   ( n 2 ) 10 n 2   ( n 2 ) First, we prove the right inequality (the upper bound): Second, we prove the left inequality (the lower bound):

19. Establishing order of growth using limits Note that the first two cases mean that t (n) ∈ O(g(n)) , the last two mean that t(n) ∈  (g(n)) , and the second case means that t(n) ∈  (g(n)) . L’Hopital’s rule Stirling’s formula

20. Establishing order of growth using limits

21. Establishing order of growth using limits

22. Establishing order of growth using limits

23. Basic Efficiency Classes