Я пытался доказать / опровергнуть вышесказанное, я доказал, что если f (n) равно Θ (h (n)) и g (n) = O (h (n)), то f (n) +g (n) - это O (h (n)), но теперь, когда я пытаюсь доказать / опровергнуть, f (n) + g (n) также является Ω (h (n), я сталкиваюсь с проблемой. Ниже мой подход.
Из заданного,
Существует b, c> 0 такое, что bh (n) = 0 такое, чтоg (n) <= ah (n) </p>
Я доказал O (h (n)), добавив два вышеуказанных неравенства, но формально доказать / опровергнуть нижнюю границу я застрял, поскольку у меня нет нижнейпривязан к g (n), но имеет нижнюю границу только к f (n).
Также я запутался, если обозначение big-oh всегда состоит из строгих неравенств или нет, если f (n)Θ (h (n)) имеет место следующее утверждение:
Существует b, c> 0 такое, что bh (n) =
Спасибо.