Notazione asintotica

Question

Questo è un problema su Notazione asintotica Dall'assegnazione di MIT OpenCourse Introduzione all'algoritmo:
Per ciascuna delle seguenti affermazioni, decidi se lo è sempre vero, Mai vero, o a volte vero per funzioni asintoticamente non negative f e g. Se è sempre vero o Mai vero, spiega perchè. Se è a volte vero, Dai un esempio per il quale è vero e uno per il quale è falso.

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

Io penso che sia Mai vero. Ecco la mia prova:

   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)

Il risultato contraddice con g(n) ≠ O(f(n)) (Big-O note). Allo stesso modo,

   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)

che contraddice con f(n) ≠ O(g(n)) (Big-O note).

La soluzione dice che lo è a volte vero:

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.

Dove ho sbagliato nella mia prova? Inoltre, non riesco a capire la soluzione. ||n*sin(n)|| sembra Norma vettoriale per me.

Answer 1

Il primo non è vero: da questo f(n) ≠ O(g(n)) non segue questo: f(n) = w(g(n)). Le due funzioni potrebbero intersecarsi ad un certo punto e poi schiaffeggiare i luoghi, l'altro diventa più grande (se uso parole semplici).

La funzione che hanno scelto è proprio questo caso: per n <= 1 il primo f (n)> g (n) e esiste ns per la quale g (n)> f (n) (ad esempio pi / 2).

Answer 2

Penso n*sin(n) mostra solo che è una funzione che continua a diventare più grande di f(n) = 1 per i valori successivi di n anche per tutte le scelte di a moltiplicatore costante Utilizzato per definire Big O & quindi f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

Una funzione ingenuamente scelta come g(n) = 2*sin(n) Non farà bene qui. Si potrebbe pensare che ciò continuerebbe anche ad alternare f(n) = 1 , ma g(n) = O(f(n)) : M*f(n) > g(n) for M = 3 eccetera