Доказательство Θ (f (x)) сложнее, чем доказательство O (f (x)), поэтому многие люди не беспокоятся. Однако в этом случае на самом деле правильно, что на месте объединение двух отсортированных списков размера n равно O (n) для всех возможных входов , а не Θ (n).
Очевидно, слияние копий два списка размером n не могут быть лучше, чем O (n), потому что копируются 2 * n элемента. Однако слияние на месте может быть реализовано в Ω (1) для наилучших сценариев. Это простой случай, когда все элементы первого списка меньше или равны элементам второго списка. Алгоритм слияния может обнаружить эту ситуацию в O (1) и ничего не делать, если элементы уже находятся в правильном порядке, следовательно, Ω (1) для лучшего случая.
Вывод: на месте объединение - это не Θ (n), а вместо этого Ω (1). На самом деле, на месте слияния с дополнительной памятью может быть Ω (1) и O (n), но без дополнительной памяти требуется O (n log n) для объединения двух списков размера n, поэтому очевидно, что вопрос не об этом деле.
Поэтому проще просто сказать O (n) и не беспокоиться о деталях на месте против copy слияния. Кроме того, обычно то, что беспокоит программистов, является наихудшим случаем, а средний случай - не лучшим.
редактировать 1
Во многих случаях, когда люди говорят O (f (n)), они имеют в виду Θ (f (n)) сложность наихудшего случая. Объединение на месте также Θ (n) для наихудшего случая, как и объединение копий.
редактировать 2
Люди обычно ссылаются на все возможные варианты, когда говорят о сложности. Если наихудший случай Θ (f (x)), а лучший случай Θ (g (x)), то технически правильно написать, что O (f (x)) и Ω (g (x)) плотны для всех возможные случаи.
Аналогично, если копировать массив - это Θ (n), то нет смысла говорить, что это O (2 n ). Это было бы технически правильно, но очень редко встречается использование большой буквы О.