Обозначение Ландау: сумма большого O <= большого O суммы

Question

Я хотел бы показать, что: O (f_1 (n) + f_2 (n) + .. + f_k (n)) <= O (f_1 (n)) + O (f_2 (n)) + ... + O (f_k (n)) верно. </p>

Моя интуиция, почему справедливо неравенство, заключается в том, что в обоих направлениях:

<=: Мы суммируем все константы Os на LHS и помещаем их в O () на RHS. </p>

Теперь я не уверен, возможно ли даже равенство.

Кстати: я знаю, что O (f (n)) на самом деле является набором, поэтому> = является злоупотреблением нотацией.

Спасибо, Энди

Answer 1

В будет доминирующая функция

Итак

И наоборот доминирует

Итак

И тогда вы получите равенство