for (int front = 1; front < intArray.length; front++)
{
for (int i = 0; i < intArray.length - front; i++)
{
if (intArray[i] > intArray[i + 1])
{
int temp = intArray[i];
intArray[i] = intArray[i + 1];
intArray[i + 1] = temp;
}
}
}
The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.
The outer loop is iterating: n times.
So you get n * (the sum of the numbers 1 to n)
Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )
Which would be (n^3) + (n^2)/2 = O(n^3) ?
I am positive I am doing this wrong. Why isn't O(n^3)?
The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable. Also, the best case time complexity will be O(n), it is when the list is already sorted.
The Bubble Sort algorithm utilizes two loops: an outer loop to iterate over each element in the input list, and an inner loop to iterate, compare and exchange a pair of values in the list. The inner loop takes (N-1) iterations while the outer loop takes N iterations.
Since each pass places the next largest value in place, the total number of passes necessary will be n−1. After completing the n−1 passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubbleSort function.
Summary. Bubble Sort is an easy-to-implement, stable sorting algorithm with a time complexity of O(n²) in the average and worst cases – and O(n) in the best case.
You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n - 1, the third n - 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i
work.
Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n2).
You're making an error by trying to combine these two strategies. It's true that the outer loop does n work the first time, then n - 1, then n - 2, etc. However, you don't multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.
Hope this helps!
Your inner loop is iterating, IN TOTAL, as you said n + (n-1) + (n-2) + (n-3) + ... + 1 times. So it is O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With