Asymptotic Analysis in Data Structures and Analysis

Asymptotic Analysis

1. Asymptotic Analysis Rachana Mehta

2. Algorithmic Analysis Why the algorithmic analysis is necessary ?

3. Algorithmic Analysis Why the algorithmic analysis is necessary ? Efficient : Less Running Time Less Memory Used Efficiency of a Algorithm/Function based on the amount of input

4. Algorithmic Analysis Why the algorithmic analysis is necessary ? Efficient : Less Running Time : Time Complexity Less Memory Used : Space Complexity Efficiency of a Algorithm/Function based on the amount of input

5. How can we measure the running time of a algorithm ? Execution ? Is it a good choice ?

6. Measuring the Running Time with a Pseudo-Code Generalize language/flow/stepwise instructions for implementing a algorithm/function Primitive Operation : Low level Operations : Data Assignment Control Statements (break,continue, function call,return) Arithmetic or Logical Operation

7. Measuring the Running Time with a Pseudo-Code Generalize language/flow/stepwise instructions for implementing a algorithm/function Programming Constructs: for loop, while loop, do-while loop if-else statement

8. Asymptotic Notation Asymptotic notations are the mathematical notations used to describe the running time of an algorithm Three Main Asymptotic Notation : Big-O Notation Omega Notation Theta Notation

9. Asymptotic Notation Big-O Notation : Upper Bound : Worst Case Analysis A Function f(n) belongs to the set O(g(n)), if there exist a positive constant c such that f(n) lies between 0 and c*g(n), for sufficiently large n. O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

10. Asymptotic Notation Omega Notation : Lower Bound : Best Case Analysis A Function f(n) belongs to the set Ω(g(n)), if there exist a positive constant c such that f(n) lies above c*g(n), for sufficiently large n. Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

11. Asymptotic Notation Theta Notation : Average Case Analysis A Function f(n) belongs to the set ϴ(g(n)), if there exist a positive constant c 1 and c 2 such that f(n) lies between c 1 *g(n) and c 2 *g(n), for sufficiently large n. Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}

12. Rules for Order Arithmetic : Multiplicative Constants O(k * f(n)) = O(f(n)) Addition Rule O(f(n) + g(n)) = max(f(n), g(n)) Multiplication Rule O(f(n) * g(n)) = O(f(n)) * O(g(n)) Examples: O(1000n) = O(n) O(n 2 + 3n + 2) = O(n 2 ) O(3n 3 + 6n 2 - 4n + 2) = O(3n 3 ) = O(n 3 ) If f(x) = n 2 * log n = O(n 2 logn)

13. Asymptotic Growth Table

14. Examples for (i = 0; i < n; i++) cin>>A[i];

15. Examples for (i = 0; i < n; i++) for (j = 0; j < n; j++) cin >> A[i][j];

16. Examples for (i = 0; i < n; i++) for (j = 0; j < i; j++) cin >> A[i][j];

17. Examples for (i = 0; i < n; i++) cin>>B[i]; for (i = 0; i < n; i++) for (j = 0; j < i; j++) cin >> A[i][j];

18. Examples for (i = 0; i < n; i++) for (k = 0;k < n; k++) cin>>B[k]; for (j = 0; j < 2*n; j++) cin >> “Hello”; cin >> A[j];

19. Examples for (i = 0; i < n; i++) for (k = 0;k < n; k++) cin>>B[k]; for (m = 0; m < n; m++) for (j = 0; j < 2*n; j++) cin >> “Hello”; cin >> A[j];

20. Examples int i = 0; int A[100]; int n =100; Take a number for “rollno” from user while(( A[i] != rollno) && (i<n)) i++; if (i > n) cout << "not found"; else cout << "found";

21. Examples int i = n; while( i>=1) x = x+1 ; i = i/2;

22. Insertion Sort - Sample

23. Insertion Sort - Algorithm

24. Insertion Sort

25. Insertion Sort

26. Insertion Sort