ANALYSIS OF ALGORITHMS
Introduction
Algorithm analysis is a study that provides theoritical estimation for the required resources of an algorithm to solve a specific problem. It's based on two factors: Time Complexity and Space Complexity
We know that for a given problem, there can be n no. of algorithms that can solve the same problem.(For example; for sorting problem we have quick sort, selection sort, bubble sort, insertion sort, merge sort etc.). So algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.
The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)
Run time Analysis
It is the process of determining how processing time increases as the size of the problem (input size) increases.
Input size is the number of elements in the input, and depending on the problem type, the input may be of different types. The following are the common types of inputs:
- Size of an array.
- Polynomial Degree.
- No. of elements in a matrix.
- Number of bits in the binary representation of the input.
- Vertices and edges in a graph.
Rate of Growth
The rate at which the running time increases as a function of input is called rate of growth.
| Time Complexity | Name |
|---|---|
| 1 | Constant |
| logn | Logarthmic |
| n | Linear |
| nlogn | Linear Logarthmic |
| n2 | Quadratic |
| n3 | Cubic |
| 2n | Exponential |
Types of Analysis
- Worst Case: Defines the input for which the algorithm takes long time.
- Best Case: Defines the input for which the algorithm takes least time.
- Worst Case: Defines the input for which the algorithm takes average time. Provides the prediction about the runtime of the algorithm.
Asymptotic Notations
Asymptotic Notations are the expressions that are used to
represent the complexity of an algorithm.
Types:
- Big-O Notation (Ο): Big O notation specifically describes worst case scenario.
- Omega Notation (Ω): Omega(Ω) notation specifically describes best case scenario.
- Theta Notation (θ): Theta(θ) notation represents the average complexity of an algorithm.
That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!