[Solved]: Extra space of MergeSort

Problem Detail: 

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort log n times. mergeRoutine is a tail call, and it doesn't add to the call stack.

The extra space I need equals to n + log n. How can the extra space be O(n)?

I think we just consider log n negligible.

public class MergeSort {      private int[] array;     private int[] helper;      public MergeSort() {         this.array = array;         this.helper = new int[array.length];     }      public void sort() {         sort(0, array.length - 1);     }      private void sort(int start, int end) {         if (end > start) {             int middle = (start + end) / 2;             sort(start, middle);             sort(middle + 1, end);             mergeRoutine(start, middle, end);         }     }      private void mergeRoutine(int start, int middle, int end) {         for (int i = start; i <= end; i++) {             helper[i] = array[i];         }         int k = start;         int i = start;         int j = middle + 1;         while (i <= middle && j <= end) {             if (helper[i] <= helper[j]) {                 array[k] = helper[i];                 i++;             } else {                 array[k] = helper[j];                 j++;             }             k++;         }          // Copy the rest. Either of the while loops works, not both.         while (i <= middle) {             array[k] = helper[i];             i++;             k++;         }     } } 

Asked By : Maksim Dmitriev

Answered By : jkff

$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.

E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n < 2n$ and $2n \in O(n)$).

However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 < k n$ for all sufficiently large $n$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44193

 Ask a Question

 Download Related Notes/Documents