This is a homework question for a data structures and algorithms course. I'm not looking to have anyone do my homework for me. Just hoping someone can tell me if I'm approaching this appropriately.
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi) {
if (hi <= lo) return;
int[] aux = new int[a.length];
int mid = (hi + lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi, aux);
}
private static void merge(int[] a, int lo, int mid,
int hi, int[] aux) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
for (int k = lo; k <= hi; k++) {
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if(aux[j] < aux[i])
a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
The only difference between this implementation and the typical implementation (that has been given in our class), is that the aux array is redefined on every recursive call to sort, versus only being defined once in the public sort method in the typical case. The typical case has running time O(nlog(n)), and a space complexity of O(n).
My task is to determine the running time and space complexity of the shown modified implementation of mergesort. As far as I can tell, the running time is not changed, so it is still O(nlog(n)), and the space complexity is also O(nlog(n)). My logic in coming to this conclusion is that the sort method allocates an array of size n each time it is called, and it is called a total of log(n) times.
So far I've had a difficult time wrapping my head around space and time complexities. Am I thinking about this one correctly, or am I way off?
Any pointers greatly appreciated.
You are right, the space complexity is O(n*logn), but it needs some clarification.
My logic in coming to this conclusion is that the sort method allocates an array of size n each time it is called, and it is called a total of log(n) times.
Actually, sort is called a total of n times during the mergesort, but the maximum recursion depth is logn during the process. Let's draw a tree of recursive calls:
sort
/ \
sort sort
/\ /\
sort sort sort sort
...
On each level, each sort function performs half of the work of its parent. So, on level 0 (root node), sort has n iterations, on level 1 each of two sorts has n/2 running time (together it is n), on level 2 each of four sorts has n/4 etc. Combined, each level does n iterations, and since the depth of the tree is log n, you get O(n*logn) time complexity.
However, in your case aux allocates n elements, regardless of the current depth, and there are n invocations of sort, so at the first glance one could conclude that the space complexity is O(n*n) = O(n^2). It is not because once we are finished with each recursive call, allocated space is freed, and there are maximum of logn recursive calls.
Notice that aux unnecessary allocates array of n elements each time. You can improve the algorithm if you declare aux in the merge function and set the appropriate length, something like this:
private static void merge(int[] a, int lo, int mid, int hi) {
int[] aux = new int[hi - lo + 1];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
aux[k - lo] = a[k];
for (int k = lo; k <= hi; k++) {
if (i > mid)
a[k] = aux[j++ - lo];
else if (j > hi)
a[k] = aux[i++ - lo];
else if(aux[j - lo] < aux[i - lo])
a[k] = aux[j++ - lo];
else
a[k] = aux[i++ - lo];
}
}
HTH.