Disequazione
salve a tutti, qualcuno può spiegarmi formalmente come mai è valida questa disequazione:
\( \sum_{i=n/2}^{n}log_2(i)\geq \frac{n}{2}log_2(\frac{n}{2}) \)
grazie mille
\( \sum_{i=n/2}^{n}log_2(i)\geq \frac{n}{2}log_2(\frac{n}{2}) \)
grazie mille
Risposte
Potremmo provare a ragionare insieme (ti avverto che non ho la risposta), tu che idee ti sei fatto?
uhm sembrerebbe interessante! Io sono come gio73, non ho la risposta neanche io. Ma dove hai preso questa disequazione? magari scrivi la consegna dell'esercizio, così è più facile capire come risolvere l'esercizio..
Poi prova a postare qualche tuo tentativo..
Poi prova a postare qualche tuo tentativo..
Dobbiamo dimostrare che $ sum_{i= n/2}^n log_2(i) >= n/2 *log_2(n/2)$
($n$ deve essere un intero positivo pari, altrimenti non ha senso la scrittura)
Dato che la funzione logaritmo è crescente, si ha $log_2 (i) >= log_2 (n/2)$ per ogni $i in {n/2, ... ,n}$.
Dunque $sum_{i= n/2}^n log_2(i) >= sum_{i= n/2}^n log_2(n/2)$
Ora "porto fuori" dalla sommatoria $log_2 (n/2)$ (posso farlo perchè non dipende da $i$), ottenendo $log_2 (n/2) * sum_{i= n/2}^n 1$.
Ora, quanto fa $sum_{i= n/2}^n 1$?
($n$ deve essere un intero positivo pari, altrimenti non ha senso la scrittura)
Dato che la funzione logaritmo è crescente, si ha $log_2 (i) >= log_2 (n/2)$ per ogni $i in {n/2, ... ,n}$.
Dunque $sum_{i= n/2}^n log_2(i) >= sum_{i= n/2}^n log_2(n/2)$
Ora "porto fuori" dalla sommatoria $log_2 (n/2)$ (posso farlo perchè non dipende da $i$), ottenendo $log_2 (n/2) * sum_{i= n/2}^n 1$.
Ora, quanto fa $sum_{i= n/2}^n 1$?
"Gi8":
Dobbiamo dimostrare che $ sum_{i= n/2}^n log_2(i) >= n/2 *log_2(n/2)$
($n$ deve essere un intero positivo pari, altrimenti non ha senso la scrittura)
Dato che la funzione logaritmo è crescente, si ha $log_2 (i) >= log_2 (n/2)$ per ogni $i in {n/2, ... ,n}$.
Dunque $sum_{i= n/2}^n log_2(i) >= sum_{i= n/2}^n log_2(n/2)$
Ora "porto fuori" dalla sommatoria $log_2 (n/2)$ (posso farlo perchè non dipende da $i$), ottenendo $log_2 (n/2) * sum_{i= n/2}^n 1$.
Ora, quanto fa $sum_{i= n/2}^n 1$?
grazie mille
"gio73":
Potremmo provare a ragionare insieme (ti avverto che non ho la risposta), tu che idee ti sei fatto?
"21zuclo":
uhm sembrerebbe interessante! Io sono come gio73, non ho la risposta neanche io. Ma dove hai preso questa disequazione? magari scrivi la consegna dell'esercizio, così è più facile capire come risolvere l'esercizio..
Poi prova a postare qualche tuo tentativo..
non avevo proprio idea, comunque era estratto da un esercizio di analisi della complessità temporale di un algoritmo
vi ringrazio lo stesso per le risposte! 
Faccio notare,come spunto di riflessione,che quella disequazione può essere riscritta nella forma
$k(k+1)*...*(2k-1)*2k>=k^k$ $AA k in NNhArr(k+1)*..(2k-1)*2k>=k^(k-1)$ $AA k in NN$(1) o,se preferite,
$D_(2k,k)>=D _(k,k-1)^("(r)")$ $AA k in NN$:
forse questa cosa può essere interessante osservarla in un'ottica combinatoria o,alternativamente a quanto fatto da Gi8,
verificarla con procedimento induttivo operando sulla sua forma espressa dalla (1).
Saluti dal web.
$k(k+1)*...*(2k-1)*2k>=k^k$ $AA k in NNhArr(k+1)*..(2k-1)*2k>=k^(k-1)$ $AA k in NN$(1) o,se preferite,
$D_(2k,k)>=D _(k,k-1)^("(r)")$ $AA k in NN$:
forse questa cosa può essere interessante osservarla in un'ottica combinatoria o,alternativamente a quanto fatto da Gi8,
verificarla con procedimento induttivo operando sulla sua forma espressa dalla (1).
Saluti dal web.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo