in Algorithms
385 views
3 votes
3 votes
Worst case and best case space complexity of merge sort is ___________________________
in Algorithms
by
385 views

2 Answers

4 votes
4 votes
Best answer
Merge sort requires an auxiliary array (as work space) to store it's intermediate result. and it's divide and concur solution so requires stack overhead which is o(logn)   so total space complexity : O(n) + O( logn)  it's in best case as well as worst case.
selected by
–1 vote
–1 vote
I think Best is log n

Worst is  n

1 comment

No merge sort needs O(n + logn ) space which is equal to O(n) in worst and best case as we divide array into equal parts so O(logn) and then merge them again in one n sized array so space as O(n)
0
0

Related questions