0 Replies - 227 Views - Last Post: 23 January 2014 - 02:56 AM Rate Topic: -----

#1 google_interview  Icon User is offline

  • New D.I.C Head

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

Space complexity for Merge Sort

Posted 23 January 2014 - 02:56 AM

Hello there! :bigsmile:



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)

Link1
Link 2
Link 3


What am I missing here? :surrender:

This post has been edited by google_interview: 23 January 2014 - 02:58 AM


Is This A Good Question/Topic? 0
  • +

Page 1 of 1