Come dimostrare le relazioni big-o

Question

Ehi, il titolo è probabilmente un po 'fuori, quindi per favore correggilo se sai come metterlo meglio.

Come compito a casa ho ricevuto diversi compiti lungo la seguente:

Sia f (n) e g (n) tramite funzioni asintoticamente positive. Dimostrare o confutare ciascuna delle seguenti congetture.

a. f(n) = O(g(n)) implies g(n) = O(f(n)) 

Ora, la mia vera domanda è: come faresti a provarlo in modo formale? So che quanto sopra sarebbe facile dato che potrei facilmente fornire un contro esempio per confutarlo, ma per il gusto dell'argomento diciamo che vogliamo fare questo senza contro-esempi, poiché ovviamente questo continua con altri esempi dove questo non funzionerà

Io sono un po 'bloccato, ho le seguenti disuguaglianze redatto (con < = essendo minore o uguale a)

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

Ma io sono incerto come avrei combinare questi 2 disequazioni in un unico (in) equazione e confutarlo. Sono certo che questo è qualcosa di abbastanza semplice che ho semplicemente trascurato e che sono piuttosto stupido al momento - ma qualsiasi suggerimento/esempi concreti su come farlo sarebbe grandioso, così che dovrei essere in grado di lavorare resto di queste domande da solo.

Answer 1

Perché vuoi confutarlo senza utilizzare un controesempio? Questo è il modo più diretto per smentire un reclamo.

Se dovessi provarlo, ovviamente non potresti utilizzare un controesempio. In questo caso, il contropositivo può funzionare molto bene - presuppone che l'affermazione sia falsa, e quindi mostrare come ciò porti a un'inconsistenza logica.

In questo caso, si inizia con f(n) <= c1 * g(n) true, poiché questo è il significato di f(n) = O(g(n)). Ora vuoi supporre che g(n) <= c2 * f(n) sia vero per tutti f e g (quest'ultima parte è molto importante, perché puoi certamente scegliere f e g in modo che sia vero) e mostrare perché questo non può funzionare. Il mio suggerimento per te: scegli uno f e un g in modo che non possa funzionare e mostra che non può funzionare a tua scelta tra c1 e c2.

Answer 2

Alcuni suggerimenti:
Non dimenticare che f(n) = O(g(n)) è un set notation ed è possibile convertirlo in una forma matematica delle disuguaglianze.

operazioni semplici si può fare con la O -notation:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), se c è costante
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(The Art of Computer Programming, vol 1 - Il O -Notation) relativo