educative.io

Time complexity of js sort

Courses
,
#1

Many solutions in two-pointer section use Javascript built-in array.sort(). And the explanation states that it takes O(n) space complexity. Based on what I understand, JS sort() is implemented using quicksort, which should be O(1) space complexity. Can someone explain this?

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5554621957275648

#2

Hey Deqian_Duan!

The lesson says, “The space complexity of the above algorithm will be O(N) which is required for sorting if we are not using an in-place sorting algorithm.”
Moreover, the space complexity of quicksort is O(log n). In the worst case, it is O(N).

Thank you for asking the question. We hope Educative has inspired you to further your learning.