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
