can anyone explain how the space complexity for merge sort is O(N)?
Space Complexity
@dare_devil_007
Mergesort, if implemented to create arrays in the recursive calls, will create many of them, but they won’t coexist at the same time. In every recursive call you create an array (or 2 depending on an implementation) for merging and they take no more than O(n) space, and then when the merging is done, these arrays are deleted and some new ones will be created after a moment in some other recursive call. If you counted how much space all the arrays that ever have been created took, it’d be O(n log n), but you don’t need to care about this information - you don’t need more than O(n) space, because when you need to create an array, all the other ones don’t longer exist and don’t occupy any memory. Note that you can simply declare 2 - or 3 - arrays in the beginning, each the length of n, and then store the sequence in one of them, while using the other for merging, it will improve the performance as well as show you beyond doubt there’s no need for more than O(n) of memory.
1 Like
i hope your doubt is cleared if yes dont forget to mark it as resolved 
1 Like