Функция в Big-O, но не в Little-O

Question

Я ищу простой пример функции f (n), которая является Big-O какой-то другой функции g (n), но не является Little-o для g (n). Другими словами, некоторые f (n) такие, что f (n) есть O (g (n)), но не o (g (n)).

Самый простой случай, о котором я могу подумать, это f (n) = n, g (n) = n. f (n) явно O (g (n)). В классе мы узнали, что одно из определений обозначений little-o состоит в том, что f (n) / g (n) при n -> бесконечности стремится к 0. В этом случае f (n) / g (n) при n идет до бесконечности приближается к 1, поэтому f (n) равно , а не o (g (n)).

Правильны ли эти логи c? Я что-то упустил?

Answer 1

Да, ваши рассуждения верны, и ваш вывод верен.

Другой способ думать об этом состоит в том, что O(g) - это набор функций, которые не растут асимптотически быстрее, чем g, o(g) - это набор функций, которые асимптотически растут медленнее, чем g. Таким образом, если f растет с той же асимптотикой c, что и g, то f находится в O(g), но не o(g). Набор o(g) является подмножеством O(g), а разность наборов O(g) \ o(g) = Θ(g).

---

Как педант, я вынужден отметить, что вы запросили функцию " , f (n), то есть Big-O некоторой другой функции, g (n) " (выделение мое), поэтому вы должны выбрать другую функцию, например g(n) = 2n, чтобы она была некоторые другие функции. ; -)