educative.io

Bubble Sort (Time Complexity) - Mastering Data Structures and Sorting

Courses
,
#1

Wondering if the worst space is O(n) instead of O(1)

Course: Mastering Data Structures and Sorting Algorithms in JavaScript - Learn Interactively
Lesson: https://www.educative.io/courses/mastering-data-structures-and-sorting-algorithms-in-javascript/q2AJwmrkW03

#2

Hi @Amanda_Varella ,

The space complexity of bubble sort is O(1) because the algorithm only requires constant additional memory to store into temporary variables for swapping data.

According to the provided code of our bubble sort algorithm in the given lesson, the worst case space complexity is O(1) because we didn’t use any additional memory.

If and only if a scenario comes, where the array is not present in the memory as explained in the “Worst Space” section of the lesson. Only for this case, we would require additional O(n) space to load the array into the memory (where n is the number of elements in the array).

I hope this answers your query.
Thanks!

Happy Learning :slight_smile:

#4

Thanks Komal!
I am struggling to think of how the array would not be present in the memory.
Are you able to explain a bit more on this?

Thanks!