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)
What am I missing here?
This post has been edited by google_interview: 23 January 2014 - 02:58 AM