На пальцах - можно и складывать и брать большее. Но последнее - более точная оценка. Но на самом деле надо формально расписать по определению. Что значит первая часть O(N)? Для некоторых чисел N1 и С1, при N>N1 первая часть алгоритма делает менее С1*N операций. Аналогично, при N>N2, вторая часть выполняет менее С2*log(N) операций.
Итого имеем, при N>max(N1,N2), всего выполняется менее C1*N+C2*logN операций. Если взять C = max(C1, C2), то можно сверху ограничить количество операций C*(N+log N). Т.е. мы доказали, что ваш алгоритм - O(N+log N). Далее, начиная с какого-то N>N3 N > log(N). Т.е. при N> max(N1,N2,N3) можно ограничить время работы как C*(N+N) = 2*C*N = C'*N. А это уже означает, что весь алгоритм - O(N).
Из этих рассуждений должно быть понятно, что при сумме константного количество шагов можно брать O() для самого тяжелого шага. Но, если количество шагов зависит от N, то так делать нельзя, потому что в последнем шаге вылезет не константный множитель (как 2 выше), а что-то зависящее от N.
Средний
