educative.io

Doubt in Space Time Complexity

Courses
,
#1

Hi,

In Java 8, Arrays.sort() uses Quicksort for primitive types whose runtime complexity in the worst case in O(n^2) and space-time complexity is O(log(n)).

https://www.bigocheatsheet.com/

If there are objects in the array then Arrays.sort() uses mergesort (Timsort)

So, can you please explain the reason for having the space-time complexity as O(n). Are we assuming that the Arrays.sort() is using merge sort?

Thanks

#2

Agreed, I also doubt the space complexity. If a quicksort or merge sort is used to sort the input array, the space would be O(lgN) because of call stack usage in recursion.

#3

If you use the sort function implemented by the language itself, the space complexity depends on the language you used. For example, in Python, it uses Timesort to sort the array, in which the space complexity is O(n).

#4

@Ammy Google for “timsort Gaurav Sen”. It should help you understand why it is O(n)