DEV Community

Posted on • Updated on

Time & Space Complexity, Stability of Algorithm

The efficiency of any sorting algorithm is determined by time complexity & space complexity of the algorithm.

Now you have some questions in your mind that what is Time Complexity and Space Complexity.

Time Complexity

Time Complexity refers to the time taken by an algorithm to complete its execution with respect to the size of the input.
It can be represented in different forms :-

Big O notation

Big O notation represents the upper bound of the running of an algorithm. Thus, it gives the worst case complexity of an algorithm. It is widly used to analyze an algorithm as we are always interested in the worst-case scenario.

Omege notation

Omege notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an algorithm.

Theta notation

Theta notation encloses the function from above and below. It is used to analyzing the average case complexity of an algorithm.

Space Complexity

Space complexity refers to the total amount of memory used by the algorithm for a complete execution. It includes both the auxiliary memory and the input.
The auxiliary memory is the additional space occupied by the algorithm apart from the input data. Usually auxiliary memory is used for calculating the space complexity of an algorithm.

Stability of the Algorithm

A sorting algorithm is considered stable if the two or more items with the same value maintain the same relative positions even after sorting.

Time complexity, Space complexity & Stability of different Sorting Algorithm

I hope you will understand Time Complexity, Space Complexity and Stability. In our upcoming blogs, we will discuss more about Data Structure like LinkedList, Stack & Queue etc.

Thank you.