in Algorithms retagged by
525 views
3 votes
3 votes
Merge sort using linked list is better than array in terms of space complexity

true or not with explanation :)
in Algorithms retagged by
by
525 views

1 comment

The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n)
1
1

1 Answer

1 vote
1 vote
Best answer
The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, it requires O(n) space because unlike linked list we cannot put an element in between 2 adjacent elements in an array due to which it requires O(n) extra space as compared to linked list which require O(logn) extra space.  In linked list, we can insert items in the middle in O(1) extra space and O(1) time. It's better to implement merge sort with linked list than with implementing it with array.
selected by

Related questions

0 votes
0 votes
0 answers
4