educative.io

Educative

Doubt in Space Time Complexity

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

1 Like