Asymptotic Analysis

Analysis of Algorithms
Analysis of Algorithms is the determination of the amount of time, storage and/or other resources necessary to execute them.
Analyzing algorithms is called Asymptotic Analysis.
Asymptotic Analysis evaluate the performance of an algorithm.
Algorithms and Data structures course

Time complexity
Time complexity of an algorithm quantifies the amount of time taken by an algorithm.
We can have three cases to analyze an algorithm:
Worst Case.
Average Case.
Best Case.
Algorithms and Data structures course

Time complexity
Assume the below algorithm using C++ code:
Algorithms and Data structures course

Time complexity
Worst Case Analysis
In the worst case analysis, we calculate upper bound on running time of an algorithm.
Algorithms and Data structures course

Time complexity
Worst Case Analysis
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 array (example: search for number 8)․
Algorithms and Data structures course

Time complexity
Worst Case Analysis
When x is not present, the search() functions compares it with the elements of arr one by one.
Algorithms and Data structures course

Time complexity
Worst Case Analysis
Time complexity of linear search would be O(n).
Algorithms and Data structures course

Time complexity
Average Case Analysis
We take all possible inputs and calculate computing time for all of the inputs.
Algorithms and Data structures course

Time complexity
Best Case Analysis
Calculate lower bound on running time of an algorithm.
Algorithms and Data structures course

Time complexity
Best Case Analysis
Time complexity in the best case of linear search would be O(1).
Algorithms and Data structures course

Time complexity
Best Case Analysis
Algorithms and Data structures course

Time complexity
Most of the times, we do worst case analysis to analyze algorithms.
The average case 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.
Algorithms and Data structures course

Asymptotic Notations
Big-O Notation: is an Asymptotic Notation for the upper bound.
Ω Notation (omega notation): is an Asymptotic Notation for the lower bound.
Θ Notation (theta notation): is an Asymptotic Notation for both the lower and the upper bounds.
Algorithms and Data structures course

Big-O Notation
O(1)
Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function. For example swap() function has O(1) time complexity.
A loop or recursion that runs a constant
number of times is also considered as O(1).
For example the following loop is O(1).
Algorithms and Data structures course

Big-O Notation
O(n)
Time Complexity 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.
Algorithms and Data structures course

Time complexity 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.
Algorithms and Data structures course

Time complexity of a loop is considered as O(log(n)) if the loop variables are divided / multiplied by a constant amount.
Algorithms and Data structures course

Big-O Notation
How to combine time complexities of consecutive loops?
Time complexity of above code is O(n) + O(m) which can also be written as O(n+m) or O(max(n, m)).
Algorithms and Data structures course

Big-O Notation. Growth Orders
Algorithms and Data structures course

Big-O Notation. Growth Orders
Algorithms and Data structures course

Big-O Notation. Growth Orders
Algorithms and Data structures course

Big-O Notation
What is this code complexity?
Algorithms and Data structures course

Big-O Notation
Algorithms and Data structures course

Big-O Notation
What is this code complexity?
Algorithms and Data structures course