Ciao a tutti, sto cercando di capire la differenza tra un grafo sparso e un grafo denso. Analizzando le seguenti domande sembra che nel caso del grafo sparso la procedura è semplice e basta applicare le regole generali. Per il grafo denso non riesco a capire come procedere.
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo sparso, i.e., con $m = Θ(n)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n)) $
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$ corretta
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo denso, i.e., con $m = Θ(n^2)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n))$ corretta
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$
Applicando le regole generali, io ottengo come risposta la d, poichè $f(n) = O(n^2)$ e $g(n) = O(n log n)$.
Dove sbaglio? Qual è la differenza con i grafi densi?