Асимптотическая запись

Question

Это проблема для асимптотической нотации из присвоения MIT OpenCourse Введение в алгоритм :
Для каждого из следующих утверждений определите, является ли оно всегдаtrue , никогда не true или иногда true для асимптотически неотрицательных функций f и g .Если это всегда верно или никогда не верно , объясните почему.Если это иногда истинно , приведите один пример, для которого оно истинно, и один для которого оно ложно.

f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))   (both are Big-O notes)

Я думаю, что это никогда не верно ,Вот мое доказательство:

   f(n) ≠ O(g(n))
=> f(n) = w(g(n))   (little-omega note)
=> g(n) = o(f(n))   (little-o note)
=> g(n) = O(f(n))   (big-O note)

результат противоречит g(n) ≠ O(f(n)) (Big-O note).Аналогично,

   g(n) ≠ O(f(n))
=> g(n) = w(f(n))   (little-omega note)
=> f(n) = o(g(n))   (little-o note)
=> f(n) = O(g(n))   (big-O note)

, что противоречит f(n) ≠ O(g(n)) (Big-O note).

Решение говорит, что иногда истинно :

For f(n) = 1 and g(n) = ||n*sin(n)|| it is true,  
while for any f(n) = O(g(n)), e.g. f(n) = g(n) = 1, it is not true.

Где ясделано неправильно в моем доказательстве?Кроме того, я не могу понять решение.||n*sin(n)|| мне кажется векторной нормой .

Answer 1

Я думаю, n*sin(n) просто показывает, что это функция, которая становится все больше и меньше f(n) = 1 для последующих значений n даже для всех вариантов постоянного множителя , используемого для определения Big O &таким образом f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

Наивно выбранная функция, такая как g(n) = 2*sin(n), здесь не поможет.Кто-то может подумать, что это будет продолжать чередоваться вокруг f(n) = 1, но g(n) = O(f(n)) : M*f(n) > g(n) for M = 3 и т. Д.

Answer 2

Первое неверно: из этого f(n) ≠ O(g(n)) не следует этого: f(n) = w(g(n)).Две функции могут пересекаться в некоторой точке, а затем шлепать места, другая становится больше (если я использую простые слова).

Функция, которую они выбрали, как раз в этом случае: для n <= 1 первый f (n)> g (n) и существуют ns, для которых g (n)> f (n) (например, pi / 2).