Why is the total space complexity of bubble sort O(1) according to Wikipedia?

Question

Based on This article on GeeksforGeeks and the questions posted on StackExchange and Quroa, the space complexity of an algorithm is the space it takes to solve a problem including the space that the input takes, and the auxiliary space is any extra storage that the algorithm needs besides the input itself to solve the problem.

Now I get that the auxiliary space of the bubble sort is O(1) since it only takes one variable to keep track of the number of swaps we are making to see when the list is sorted (correct me if I'm wrong), but why does Wikipedia say that the total space complexity of the bubble sort is O(1) as well?

Isn't it supposed to be O(n) considering the input itself?

Answer 1

why does Wikipedia say that the total space complexity of the bubble sort is O(1) as well?

Good catch! It was corrected in the mean time. It now says the total space complexity is O(n). Quoted from the summary panel at the right:

Worst-case space complexity O(𝘯) total, O(1) auxiliary

So:

• The input has a space complexity of O(𝘯)
• In addition, O(1) is needed for the algorithm = auxiliary space
• The total space used consists of input and auxiliary space, so O(𝘯)+O(1) = O(𝘯)