CODEWITHSUNDEEP
algorithmsortingbig-obubble-sortspace-complexity
Amirreza A.
Amirreza A.

Reputation: 761

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

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?

Upvotes: 2

Views: 743

Answers (2)

trincot
trincot

Reputation: 350137

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(𝘯)

Upvotes: 2

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1529

By the term space complexity it defines that the amount of extra memory your algorithm takes. if you required to allocation an array of size N it would mean your algorithm takes O(N) extra space or more specifically auxiliary space.

But in case of bubble-sort, we can use only single variable (for swapping purpose) to make things happen.

so overall space complexity is O(N) which includes your input, and overall auxiliary space complexity is O(1)

In Wikipedia by overall space complexity it defines auxiliary space.

Upvotes: 1

Related Questions