Download as PDF, PPTX
Time Complexity of Algorithm (Analysis).pdf
- 1. ANALYSIS AND DESIGNOF ALGORITHM
- 2.
- 3. ❑Analysis of Algorithmsinvolves determining the amount of time, storage and/or other resources ❑Analyzing algorithms is called Asymptotic Analysis ❑Asymptotic Analysis evaluate the performance of an algorithm
- 4.
- 5. ❑time complexity ofan algorithm quantifies the amount of time taken by an algorithm ❑ We can have three cases to analyze an algorithm: 1) Worst Case 2) Average Case 3) Best Case ❑ Assume the below algorithm using Python code:
- 7. ❑ Worst CaseAnalysis: In the worst case analysis, we calculate upper bound on running time of an algorithm.
- 9. ❑ Worst CaseAnalysis: the case that causes maximum number of operations to be executed. ❑ For Linear Search, the worst case happens when the element to be searched is not present in the array. (example : search for number 8) 2 3 5 4 1 7 6
- 10. ❑ Worst CaseAnalysis: When x is not present, the search() functions compares it with all the elements of arr one by one.
- 11. ❑ The worstcase time complexity of linear search would be O(n).
- 13. ❑ Average CaseAnalysis: we take all possible inputs and calculate computing time for all of the inputs.
- 15. ❑ Best CaseAnalysis: calculate lower bound on running time of an algorithm.
- 16. ❑ The bestcase time complexity of linear search would be O(1).
- 18. ❑ Best CaseAnalysis: the case that causes minimum number of operations to be executed. ❑ For Linear Search, the best case occurs when x is present at the first location. (example : search for number 2) ❑ So time complexity in the best case would be Θ(1) 2 3 5 4 1 7 6 ❑ Most of the times, we do worst case analysis to analyze algorithms.
- 19. ❑ The averagecase analysis is not easy to do in most of the practical cases and it is rarely done. ❑ The Best case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t provide any information.
- 20. 1) Big ONotation: is an Asymptotic Notation for the worst case. 2) Ω Notation (omega notation): is an Asymptotic Notation for the best case. 3) Θ Notation (theta notation) : is an Asymptotic Notation for the worst case and the best case.
- 21.
- 22. 1) O(1) ➢ Timecomplexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other nonconstant time function. For example swap() function has O(1) time complexity.
- 23. ➢ A loopor recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1).
- 24. 2) O(n) ➢ TimeComplexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example the following loop statements have O(n) time complexity.
- 26.
- 27. 3) O(nc ) ➢ Timecomplexity of nested loops is equal to the number of times the innermost statement is executed. For example the following loop statements have O(n2 ) time complexity
- 28.
- 29.
- 30. 4) O(Logn) ➢ TimeComplexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.
- 31. 4) O(Logn) ➢ AnotherExample
- 32. 5) O(LogLogn) ➢ TimeComplexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant.
- 33. 5) O(LogLogn) ➢ AnotherExample
- 35. ❑ How tocombine time complexities of consecutive loops? ❑ Time complexity of above code is O(n) + O(m) which is O(n+m)
- 37. ❑ Find thecomplexity of the below program:
- 38. ❑ Solution: TimeComplexity is O(n). Even though the innerloop is bounded by n, but due to break statement it is executed only once.
- 39. www.YourCompany.com © 2020 CompanynamePowerPoint Business Theme. All Rights Reserved.