# Space complexity for Merge Sort

Page 1 of 1

## 0 Replies - 277 Views - Last Post: 23 January 2014 - 02:56 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=338767&amp;s=6d44dbb361a2231a81df7d9c9dd2eb61&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

Reputation: 1
• Posts: 49
• Joined: 27-December 13

# Space complexity for Merge Sort

Posted 23 January 2014 - 02:56 AM

Hello there!

I've been reading up on the Merge Sort algorithm.
The time complexities are as follows:
1) Divide step: O(constant)
2) Recursion step: O (n * log (n))
3) Final merge: O (n)

Now, I am unable to understand how space complexity is computed
a ) For arrays: in every level of the tree we have n elements; thus; the overall space complexity (# arrays) should be n * log(n). However, it is said to be O(n) - why?
b ) For linked lists: Same as with arrays. Should be n * log (n). Yet, it is assumed to be O (log n)