Analyze the following sorting algorithm:
for (int i = 0; i < SIZE; i++) { if (list[i] > list[i + 1]) { swap list[i] with list[i + 1]; i = 0; } } I want to determine the time complexity for this, in the worse case...I don't understand how it is O(n^3)
Clearly the for loop by itself is O(n). The question is, how many times can it run?
Every time you do a swap, the loop starts over. How many times will you do a swap? You will do a swap for each element from its starting position until it reaches its proper spot in the sorted output. For an input that is reverse sorted, that will average to n/2 times, or O(n) again. But that's for each element, giving another O(n). That's how you get to O(n^3).
I ran an analysis for n = 10 and n = 100. The number of comparisons seems to be O(n3) which makes sense because i gets set to 0 an average of n / 2 times so it's somewhere around n2*(n/2) comparison and increment operations for your for loop, but the number of swaps seems to be only O(n2) because obviously no more swaps are necessary to sort the entire list. The best case is still n-1 comparisons and 0 swaps of course.
For best-case testing I use an already sorted array of n elements: [0...n-1].
For worst-case testing I use a reverse-sorted array of n elements: [n-1...0]
def analyzeSlowSort(A): comparison_count = swap_count = i = 0 while i < len(A) - 1: comparison_count += 1 if A[i] > A[i+1]: A[i], A[i+1] = A[i+1], A[i] swap_count += 1 i = 0 i += 1 return comparison_count, swap_count n = 10 # Best case print analyzeSlowSort(range(n)) # ->(9, 0) # Worst case print analyzeSlowSort(range(n, 0, -1)) # ->(129, 37) n = 100 # Best case print analyzeSlowSort(range(n)) # ->(99, 0) # Worst case print analyzeSlowSort(range(n, 0, -1)) # ->(161799, 4852) Clearly this is a very inefficient sorting algorithm in terms of comparisons. :)
Okay.. here goes.. in the worst case lets say we have a completely flipped array..
9 8 7 6 5 4 3 2 1 0
Each time there is a swap.. the i is getting resetted to 0.
Lets start by flipping 9 8 : We have now 8 9 7 6 5 4 3 2 1 0 and the i is set back to zero.
Now the loop runs till 2 and we have a flip again.. : 8 7 9 6 5 4 3 2 1 0 i reset again.. but to get 7 to the first place we have another flip for 8 and 7. : 7 8 9 6 5 4 3 2 1 0
So the number of loops are like this :
T(1) = O(1) T(2) = O(1 + 2) T(3) = O(1 + 2 + 3) T(4) = O(1 + 2 + 3 + 4) and so on..
Finally For nth term which is the biggest in this case its T(n) = O(n(n-1)/2).
But for the entire thing you need to sum all of these terms up Which can be bounded by the case Summation of (T(n)) = O(Summation of (n^2)) = O(n^3)
Addition Think of it this way: For each element you need to go up to it and bring it back.. but when you bring it back its just by one space. I hope that makes it a little more clear.
Another Edit If any of the above is not making sense. Think of it this way : You have to bring 0 to the front of the array. You have initially walk up to the zero 9 steps and put it before 1. But after that you are magically transported (i=0) to the beginning of the array. So now you have to walk 8 steps to the zero and then bring it in two's position. Again Zap! and you are back to start of the array. How many steps approximately you have to take to get to zero each time so that its right at the front. 9 + 8 + 7 + 6 + 5 + .. this is the last term of the recurrence and so is bounded by the Square of the length of the array. Does this make sense? Now to do this for each of the element on average you are doing O(n) work.. right? Which translates to summing all the terms up.. And we have O(n^3).
Please comment if things help or don't make sense.
O(n^2). Not 3(int i = 0; i < SIZE - 1; i++)or you will get an index error when you try to compare withlist[i+1].