Algorithms are steps to solve a problem and there are many algorithms to solve just one problem but all of them follow different steps. All these algorithms have pros and cons and all these algorithms take different time to solve the same problem.
When solving a problem we always look for the most efficient way to solve that problem and for that we need to find the time complexity and the steps it will take an algorithm to solve the problem more efficiently. For this analysis of algorithms we use a notation called The Big O Notation.
The Big O Notation
The Big O Notation is used to find the complexity of an algorithm. It is a way to know how well an algorithm will perform when provided with a certain input. It helps programmers know about the time and space complexity of an algorithm.
For example the Big O notation of Insertion Sort in Best Case performance is O(n) or of Linear Complexity. Linear Complexity means that the steps it will take for an algorithm to complete its execution will increase or decrease with the size of input.
Other common Big O Notations are following.
- O(c)
- O(n)
- O(n^2)
- O(Log(n))
- O(nLog(n))
These notations are used to describe the time complexity of an algorithm in three cases. In:
- Best Case
- Worst Case
- Average Case
Big O Notation Of Insertion Sort
Insertion Sort is a simple sorting algorithm. It sorts a list of elements by sorting one element at a time. The Big O notation for insertion sort in different cases is following.
- Best Case Performance: O(n)
- Worst Case Performance: O(n^2)
- Average Case Performance: O(n^2)
In Best Case Performance, Big O of the insertion sort is O(n). This means the steps to complete the execution of an algorithm will increase or decrease depending on the size of the input provided. Bigger the input more time and steps it will take to get the output and vice versa.
In Worst Case Performance, Big O of insertion sort is O(n^2). This means that the steps it will take for the algorithm to complete its execution will be square to the size of the input. Bigger the size of input, more steps to complete its execution. And same goes for Average Case Performance.
zainsci