How Bubble sort fit into Quadratic(n²) time complexity in the worst case?
A question stuck on my mind and ate my two weeks of leisure time.
How Bubble sort fit into Quadratic(n²) time complexity in the worst case ? Since it won’t run on n² iterations to sort value.
for(let i = 0; i<n; i++)
for(let j=0, j<n-i; j++) {
/*swap and take higher element to n-i position
*/
}
For example, If length of the array is 4 then the cumulative result of two-loop iteration count would be 4+3+2+1 = 10 times. Not 4*4 = 16 because of inner loop condition is n-i.
Some of the web results say if we use 2 for-loop then it’s a Quadratic time complex and single for-loop is a linear time complexity. it isn’t right.
Then what’s right? we must understand a few concepts here
Time/Space complexity
Usually, any set of code (algorithm) has n number of instructions(operations). The number of operation would increase/decrease based on input values. This operation will consume processing time/memory space to execute in the system. The consumable quantity will be classified in Big O notation to measure the time/space complexity. Before knowing Big O, We must understand the base concept(Asymptomatic).
Asymptotic
It is a mathematical analysis to describe limiting input to reach the closest same behavior of exact input. For example: If f(n) = n²+ 2n, then as n becomes very large, the term 2n becomes insignificant compared to n². The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞".
Geometric analysis help to understand the above example.
Asymptote is a line that a curve approaches, as it heads towards infinity.
Big O
As explained above, the algorithm has n number of operations and operations produce time complexity. And we know a simple program will involve an enormous operation. To simplify complexity calculation, we use asymptotic analysis.
Analysis result classified into Big notation classification and Big O is the upper bound result of asymptotic. Omega O is the lower bound result.
Type of major Big O classification is
O(1) Content time — ex: hash map data structure.
O(n) Linear time — ex: finding an element in a linked list data structure.
O(n2)Quadratic time — ex:bubble/insertation/ selection sort algorithm.
O(log n)Logarithmic — ex: binary tree data structure.
O(n log n) Linearithmic — ex: Heap data structure / merge sort algorithm.
let us find the answer to the original question here. Let us take 8 elements of an unsorted array. it would take 8+ 7+6+5+4+3+2+1 = 36 iteration (repeated operation) to get sorted result in bubble sort algorithm. we write it as an equation, If we has n elements then
(n-1)+(n-2)+….(2)+(1) = n(n+1)/2
Reference:-