This algorithm is of mergesort, I know this may be looking weird to you but my main focus is on calculating space complexity of this algorithm.
If we look at the recurrence tree of mergesort function and try to trace the algorithm then the stack size will be log(n). But since merge function is also there inside the mergesort which is creating two arrays of size n/2, n/2 , then first should I find the space complexity of recurrence relation and then, should I add in that n/2 + n/2 that will become O(log(n) + n).
I know the answer, but I am confused in the process. Can anyone tell me correct procedure?
This confusion is due to merge function which is not recursive but called in a recursive function
And why we are saying that space complexity will be O(log(n) + n) and by the definition of recursive function space complexity, we usually calculate the height of recursive tree
Merge(Leftarray, Rightarray, Array) {
nL <- length(Leftarray)
nR <- length(Rightarray)
i <- j <- k <- 0
while (i < nL && j < nR) {
if (Leftarray[i] <= Rightarray[j])
Array[k++] <- Leftarray[i++]
else
Array[k++] <- Rightarray[j++]
}
while (i < nL) {
Array[k++] <- Leftarray[i++]
}
while (j < nR) {
Array[k++] <- Rightarray[j++]
}
}
Mergesort(Array) {
n <- length(Array)
if (n < 2)
return
mid <- n / 2
Leftarray <- array of size (mid)
Rightarray <- array of size (n-mid)
for i <- 0 to mid-1
Leftarray[i] <- Array[i]
for i <- mid to n-1
Right[i-mid] <- Array[mid]
Mergesort(Leftarray)
Mergesort(Rightarray)
Merge(Leftarray, Rightarray)
}
MergeSort time Complexity is O(nlgn) which is a fundamental knowledge. Merge Sort space complexity will always be O(n) including with arrays. If you draw the space tree out, it will seem as though the space complexity is O(nlgn). However, as the code is a Depth First code, you will always only be expanding along one branch of the tree, therefore, the total space usage required will always be bounded by O(3n) = O(n).
For example, if you draw the space tree out, it seems like it is O(nlgn)
16 | 16
/ \
/ \
/ \
/ \
8 8 | 16
/ \ / \
/ \ / \
4 4 4 4 | 16
/ \ / \ / \ / \
2 2 2 2..................... | 16
/ \ /\ ........................
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 16
where height of tree is O(logn) => Space complexity is O(nlogn + n) = O(nlogn). However, this is not the case in the actual code as it does not execute in parallel. For example, in the case where N = 16, this is how the code for mergesort executes. N = 16.
16
/
8
/
4
/
2
/ \
1 1
notice how number of space used is 32 = 2n = 2*16 < 3n
Then it merge upwards
16
/
8
/
4
/ \
2 2
/ \
1 1
which is 34 < 3n. Then it merge upwards
16
/
8
/ \
4 4
/
2
/ \
1 1
36 < 16 * 3 = 48
then it merge upwards
16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
16 + 16 + 14 = 46 < 3*n = 48
in a larger case, n = 64
64
/ \
32 32
/ \
16 16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
which is 64*3 <= 3*n = 3*64
You can prove this by induction for the general case.
Therefore, space complexity is always bounded by O(3n) = O(n) even if you implement with arrays as long as you clean up used space after merging and not execute code in parallel but sequential.
Example of my implementation is given below: