Algoritmi domanda notazione asintotica

Darèios89
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.

Risposte
apatriarca
Nessuna idea? Hai provato ad applicare le definizioni?

Andreufio
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.

Darèios89
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.

vict85
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}\).

Darèios89
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...... :-D

vict85
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.

Andreufio
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? :(

apatriarca
La seconda deriva dal fatto che se \(a > b\) allora \( \log_a b < 1. \)

vict85
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?

Andreufio
No perfetto. Siete stati molto gentili. Grazie 1000

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.