Extra space of MergeSort [duplicate]

Question

This question already has an answer here:

• Sorting functions by asymptotic growth 6 answers

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++;
        }
    }
}

Answer 1

$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$.