I have a question regarding the worst case bubblesort time complexity.
What I have understood from David's lecture is the following:
Let's say we have an array of 4 elements, sorted in reverse order [4,3,2,1].
So, to sort the above array into [1,2,3,4], (n-1) passes is needed.
And for each of the passes, the numbers of comparison will be lesser, starting from (n-1), (n-2), (n-3) since we have already moved the highest numbers to the right.
I am a little confused with Doug's short lecture on bubble sort. In his lecture, he mentioned that for a worst case bubble sort, n passes is needed to sort an array of reverse order to an array of increasing order.
Link to his lecture (skip to 5:22 for the time complexity analysis): https://courses.edx.org/courses/course-v1:HarvardX+CS50+X/courseware/6f10d1f2fb0548ada175ba2ed508f50c/ad2ce21f33474bed96e87005fe3eba6d/3?activate_block_id=block-v1%3AHarvardX%2BCS50%2BX%2Btype%40video%2Bblock%400da6fa2de9554ca3b8d14a50cf77b8f1
So, I am curious as to why Doug is referring to n passes instead of (n-1) passes that is required to sort an array of n elements into the correct order? Shouldn't (n-1) passes be the correct one?
Thanks