В чем разница между O(N) + O(M) и O(N + M). Есть ли?

Question

Я решаю проблемы для практики собеседования, и я не могу найти ответ на сложность времени и пространства для следующей проблемы:

Имея два отсортированных связанных списка, объедините их в третий список в отсортированном порядке. Давайте предположим, что мы используем в порядке убывания.

Один из ответов, которые мне встретились и который явно не самый эффективный, - это следующее рекурсивное решение:

Node mergeLists(Node head1, Node head2) {
    if (head1 == null) {
        return head2;
    } else if (head2 == null) {
        return head1;
    }

    Node newHead = null;
    if(head1.data < head2.data) {
        newHead = head1;
        newHead.next = mergeLists(head1.next, head2);
    } else {
        newHead = head2;
        newHead.next = mergeLists(head1, head2.next);
    }

    return newHead;
}

Теперь, когда я анализировал сложность этой функции, я столкнулся с проблемой. Я не был уверен, было ли это O(M + N) или же O(M) + O(N), Я просто не могу получить интуитивный ответ. Мне кажется логичным, что временные и пространственные сложности этой функции O(N) + O(M) или же O(max(N,M)) поскольку большее значение будет приводить к асимптотической кривой (или к рекурсивным вызовам и созданию кадров стека).

Подводить итоги:

В биг-ах нотации какая разница между O(N+M) а также O(N) + O(M) ? Есть ли? Если бы они отличались, я был бы признателен, если бы кто-нибудь смог привести простые примеры того и другого.

Answer 1

O(N) + O(M) означает функции, которые ограничены cN + dM для некоторых c а также d,

O(N + M) означает функции, которые ограничены e(N + M) для некоторых e,

Они эквивалентны, потому что:

cN + dM <= (c + d)(N + M) для некоторых c а также d,

а также

e(N + M) <= eN + eM для некоторых e,