-1

I have some confusion related to the space complexity of merge sort. It says it is O(n). However, if I look at the implementation in the wiki, it looks O(nlogn).

This is because at each recursive call, I split the array into left and right. For instance lets start at the first call for merge sort. It will split the array into two halves left and right for which we already need n space. As you can see in the wiki implementation it creates two new arrays to hold the left and right parts.

Now two recursive calls are made for the right and left halves correspondingly which will themselves divide their part into left and right which will again take space n combining the four new halves and so on.

Since all of these are recursive calls, the memory is consumed in the stack over and over again and accumulates to O(nlogn). So I think the space complexity for this particular implementation is O(nlogn).

Please provide some insights?

OmG
  • 18,337
  • 10
  • 57
  • 90
user12331
  • 486
  • 7
  • 22

1 Answers1

-1

You are close. If you are including the space of the recursive calls, it is O(n) + O(logn) which = O(n). Hopefully this addresses your question.

See this post for more.

Community
  • 1
  • 1
abalos
  • 1,301
  • 7
  • 12
  • I didn't get it. Apparently from http://en.wikipedia.org/wiki/Merge_sort, it looks O(n+n/2+n/4..1) which is O(n) basically. For eg if the initial input size is 8. The recursive calls will hold like 8-4-2-1. – user12331 Oct 21 '14 at 12:02
  • I don't think it is Lets say n=8. Then O(8+4+2+1) = O(15) is not equal to O(8+log(8)) which is O(8+3) = O(11) – user12331 Oct 21 '14 at 12:08
  • I'm not sure how to clarify it further. As n goes to infinity, since the space complexity of O(n) is added to O(log(n)), the dominant term takes over and the resulting space complexity is O(n). – abalos Oct 21 '14 at 12:08
  • Basically, because there isn't log(n) space used for each term n, it's not O(nlog(n)). For the whole set n, there is an additional log(n) space needed. I'd recommend the post I linked. They go into more detail. Unfortunately I need to take off, so I won't be able to answer any more questions for a while. – abalos Oct 21 '14 at 12:10
  • I got the last part you said. That the bigger term dominates. But for this particular implementation of wiki, I don't think it is O(n+log(n)). I just want to exactly correct. It's definitely not O(n+logn). – user12331 Oct 21 '14 at 12:10