Что будет O (n) + o (nlogn)?

Question

Что будет o (nlogn) + O (n)?

Мое предположение O (nlogn)?

f1 (n) = o (nlogn) означает для каждой константы c, существует n0 такое, что 0 < = f1 (n) < cnlogn.

И f2 (n) = O (n) означает, что существует некоторая константа c1, такая, что при n> n1, 0 < = f2 (n) < = c1n.

так что я могу получить от этого то, что существует некоторая константа c1, такая, что для n> max (n0, n1), 0 < = f1 (n) + f2 (n) < = c1 (nlogn).

Answer 1

Давайте рассмотрим асимптотические пределы этих функций и их сумму.

Во-первых, верхний предел:

F1 = o(n*log(n)), F2 = O(n) = o(n*log(n)), so 
F1 + F2 = o (n* log(n)) 

Во-вторых, нижний предел: мы знаем, F2 является O (N), но F1 может быть равен нулю для всех мы знаем, или где-то между нулем и п * журнала (п). Таким образом, мы можем с уверенностью сказать, что F1 + F2 не является o (N).

Я позволю вам положить все это в терминах 'для каждой константы C существует индекс n'.

EDIT: Дуглас указал, что большой - О, и немного-О - только верхние границы, и, строго говоря, вы ничего не можете сказать о нижних границах. Это абсолютно правильно.

Однако в программировании большую часть времени мы действительно нуждаемся в наихудших сценариях, и никто не говорит, что sqrt (n) = O (n) - что технически было бы правильным. Так что да, мы можем говорить о нижних границах, в некотором смысле, если мы имеем в виду худший случай.

Answer 2

Если f является o (n log n) и g является O (n), то g также является o (n log n), поэтому f + g является o (n log n).

У вас нет положительной нижней границы. Вы не можете сказать, что f + g не может быть o (n) или даже o (1). Функция 0 является как O (n), так и o (n log n). Итак, sqrt (n).

Знаки Big-O и little-o являются асимптотическими верхними границами для величины. Они не являются нижними границами. Большие Омега и мало-омега являются нижними границами. Theta означает, что у вас есть как верхняя граница, так и нижняя граница той же формы. Когда вы складываете две верхние границы, вы получаете верхнюю границу. У вас нет положительной нижней границы. В частности, вы не можете утверждать, что сумма не равна o (n).