Bubble Sort Time Complexity

Question

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

Answer 1

When evaluating time complexity, it's about order of magnitude estimates, not exact precision. For this reason, n - c, where c is a constant, are generally treated the same It's the order of magnitude that counts, so n, n-1, n-2,...,n-c are all treated as being n for purposes of estimation of time complexity.

Take it further. n * (n-1) evaluates to n^2 or n squared. The difference between n and n-1 is considered trivial, so the -1 is dropped. Keep in mind that in computer engineering, when you need to do time complexity evaluations, the code is probably running millions, billions, or more times or across similar amounts of data. The difference in time of a few units (or even up to n units) doesn't have as big an impact as you might think. It's more important to hunt for orders of magnitude differences than those of constants. I'd rather refine an n^4 down to n^3 than to change n to n/2. Changing n to n-1 is almost meaningless.

So, to specifically answer your question, n-1 evaluates to n in time complexity calculations. It's more like looking at a synthetic worst case time, without focusing in on the minutiae of time decay effects of linear decrease in variables.

Take it still further. If there are multiple order terms, changing the lower order terms won't have nearly as much impact as changing the highest order. Say that an algorithm has a time complexity evaluation of n^5 + n^3 + n. Changing the 3rd order code will have a minor impact, changing the 1st order n would be almost meaningless. But if you could improve code that is causing the n^5 fifth order time complexity and make it a 4th order, it would have a tremendous impact on the execution time! Of course, changing n to n-1 in all those cases would have minimal impact across the board.

Does it make more sense yet?

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)