At the beginning of this post, one's should have read the bubble sort algorithm and its implementation to understand the time complexity properly.
Read Similar Posts:
1. Bubble Sort in C++ with the algorithm
Time Complexity of Bubble Sort
The time complexity of the sorting algorithm or majority of an algorithm is measured or classified by the Big O notation. Why was Theta or Gamma notation used for the classification of the time complexity of algorithms? The answer is simple, all notation is used but the Big O notation is easy to understand and classify an algorithm time complexity.
Now, we will start to classify or describe the time complexity of Bubble sort. The time complexity of an algorithm largely depends on the input size and the number of loops run to the length of the input array in an algorithm. The input size of the bubble sort can be large. The below will show the input taking the implementation of bubble sort (c++),
for (i=1; i<=n; i++)
{
cin>>DataArray[i];
}
The time complexity for input taking will be O (1)
For the sorting and comparison, there are two loops should be run until the elements of the array have been traversed. The implementation of the comparison loops is given below for a better understanding.
for (i=1; i<=n; i++)
{
for (j=1; j<n; j++)
{
if (DataArray[j+1] < DataArray[j])
{
temp = DataArray[j];
DataArray[j] = DataArray[j+1];
DataArray[j+1] = temp;
}
}
}
The two-loop time complexity will be O (n2). If the smallest number is in the last index of the array, at that time the worst case will occur (Figure 02). The best case will occur if the array already is sorted (Figure 01) and the time complexity will be O(n). We are considering the worst case of the Bubble sort.
Fig. 01: Best time complexity of bubble sort
Fig. 02: Worst time complexity of bubble sort
Time Complexity = Input taking * Comparison of elements
= O (1) * O (n2)
= O (n2)
Time Complexity of Bubble Sort is O(n2)