Асимптотическая сложность, алгоритмы

Question

Для какого случая f(n) != O(g(n)) и g(n) != O(f(n)) верно?

У меня есть следующий ответ на этот вопрос, который я не мог понять:

Иногда верно: Для f(n) = 1 и g(n) = ||n ∗ sin(n)|| это правда, в то время как для любого f(n) = O(g(n)), например, f(n) = g(n) = 1, это не так.

Пожалуйста, помогите кому-нибудь понять:

1. В этом случае это иногда верно?Мы очень ценим объяснение с примером.
2. Что означает «||»в этом?

Answer 1

f (n)! = O (g (n)) истинно, если для любого заданного k и любого заданного N существует n> = N так, что f (n)> k * g (n) .

Пример обоих f (n)! = O (g(n)) и g (n)! = O (f (n)) , будучи истинным в одно и то же время, будет следующим: Позволяет определить f (n) = 0 для четных n и f (n) = n для нечетных n .Аналогично, давайте определим g (n) = n для четных n и g (n) = 0 для нечетных n .Теперь, очевидно, f (n)> k g (n) для всех нечетных n независимо от того, насколько большой мы выбираем k и аналогично г(n)> k f (n) для всех четных n независимо от того, насколько велик k .

Ваш пример f (n) = 1 и g (n) = || n ∗ sin (n) || также будет работать, поскольку g (n) колеблется и получаетзначение 0 для сколь угодно большого n , но также для получения сколь угодно больших значений, что достаточно для нашего определения f (n)! = O (g (n)) и g (n)! = O (f (n)) , поскольку f остается постоянной функцией 1