Algoritmi domanda notazione asintotica
Quali delle seguenti affermazioni sul comportamento asintotico è falsa?
a) [tex]b^{\log_a(n)}=\omega(\log_a(n^b))[/tex] per ogni [tex]1
b) [tex]b^{\log_a(n)}=O(n)[/tex] per ogni [tex]1
c) [tex]b^{\log_a(n)}=\Theta(n^2)[/tex] per ogni [tex]1
d) Nessuna delle precedenti risposte.
a) [tex]b^{\log_a(n)}=\omega(\log_a(n^b))[/tex] per ogni [tex]1
b) [tex]b^{\log_a(n)}=O(n)[/tex] per ogni [tex]1
c) [tex]b^{\log_a(n)}=\Theta(n^2)[/tex] per ogni [tex]1
d) Nessuna delle precedenti risposte.
Risposte
Nessuna idea? Hai provato ad applicare le definizioni?
Sono un collega di Dareios stiamo cercando di risolvere insieme l'esercizio. Siamo riusciti a capire che la C è verificata ma per la A e la B non sappiamo bene come muoverci.
Riguardando....la a) mi sembra corretta...considerando la scala degli infiniti in teoria il logaritmo rispetto ad un esponenziale dovrebbe essere sempre più lenta (asintoticamente). Mentre la b) sembra falsa.....un' esponenziale minore della funzione lineare....mi sembra di no.
Basta fare i calcoli: \(\displaystyle b^{\log_a(n)} = \bigl(a^{\log_a b}\bigr)^{\log_a n} = \bigl(a^{\log_a n}\bigr)^{\log_a b} = n^{\log_a b}\).
Quindi....dato che la b dice =O(n) e non quello che si ricava da quei passaggi é falsa? La matematica non è e non sarà mai il mio forte......

In (a) tu intendi \(\displaystyle \omega \) o \(\displaystyle \Omega \)? In ogni caso sta a te applicare le definizioni, e sinceramente non ho capito il tuo commento sulla verita/falsità di b.
Da quello che dicono altri colleghi le prime 3 sono tutte verificate. Il problema è che continuo a non capire come verificare l'esattezza delle prime due. Nella prima è omega piccolo... Il problema è che domani ho un orale e sicuramente questa mi verrà chiesta perchè non ho risposto. Sareste così gentili da spiegarmi come dimostrare le prime due?

La seconda deriva dal fatto che se \(a > b\) allora \( \log_a b < 1. \)
Per la prima basta usare che per \(b>a\), \(\displaystyle n^{\log_a b} = \omega(n)\) e \(\displaystyle n = \omega(b\log_a(n)) = \omega(\log(n)) \). Ripassati le proprietà dei logaritmi. Dubbi?
No perfetto. Siete stati molto gentili. Grazie 1000