[Algoritmi] Ricorrenza e metodo sostituzione

[mosca9]

Salve a tutti
$T(n)=\{(0, n=1; n=2), (T(n/3)+T(2n/3)+4n , n>2):}$
mi si chiede di provare con il metodo di sostituzione che tale ricorrenza è T(n)=O(n). Ho applicato il metodo e mi viene che non può essere O(n) mentre ho dimostrato che è O(nlogn). E' possibile che la consegna dell'esercizio sia sbagliata ( non mi è mai capitato che mi si chiedesse di dimostrare qualcosa che si rivelava falso e di dover fare un'altra ipotesi) o c'è un qualche trucco (tipo aggiungendo fattori costanti) per dimostrare che è O(n) e quindi ho sbagliato a interpretare l'esercizio?
Se volete metto tutti i conti.

[apatriarca]

Prova a scrivere la tua risoluzione.

[mosca9]

Passo induttivo:
T(n/3) T(2n/3)<2cn/3

T(n)<(cn/3)+(2cn/3)+4n=cn+4n=(c+4)n che non può essere mai minore di cn. Quindi ho dedotto che non può essere O(n). Ho fatto qualche errore?

[apatriarca]

Per prima cosa quella che hai scritto non è una dimostrazione, andrebbe scritta diversamente. Dovresti per esempio iniziare dicendo qualcosa come "supponiamo che $T \in O(n)$, allora deve esistere una costante $c$ tale che .. " A questo punto fai i tuoi passaggi e arrivi all'eventuale assurdo. Il tuo ragionamento mi sembrerebbe in effetti corretto.

[mosca9]

Si hai ragione, non sono stato formale, ho saltato anche il caso base, ho messo solo il tratto che porta all'assurdo molto sbrigativamente. Ho visto che a volte è possibile "far tornare" la ricorrenza sommando o sottrando dei valori all'ipotesi di partenza (ad esempio considerare cn-b con b e c da determinare nella dimostrazione) ma anche in tal caso non trovo che è O(n).

[hamming_burst]

"mosca9":Passo induttivo:
T(n/3) T(2n/3)<2cn/3

T(n)<(cn/3)+(2cn/3)+4n=cn+4n=(c+4)n che non può essere mai minore di cn. Quindi ho dedotto che non può essere O(n). Ho fatto qualche errore?

attenzione alle costanti!
$T(n/3)<= cn/3$
$T(2n/3)<= 2dn/3$

[mosca9]

$T(n)
come proseguo?

[hamming_burst]

$<=$ non minore stretto quello che vuoi dimostrare è una limitazione superiore stretta (O-grande), se minore stretto è o-piccolo.

"mosca9":$T(n)
come proseguo?

azz scusa mi son confuso su un altro caso è in effetti $c$ per entrambi i rami di recursione, ho controllato.

Perciò:
$T(n)<=cn/3+2dn/3 + 4n = (c/3+2c/3 + 4)n =$ \((c+4)n \nleq cn\) hai fatto correttamente, non è la complessità adatta cmq.

Prova con altre metodologie oppure ipotizza un'altra complessità (ovviamente $T(n) \in \Omega(n)$)

[mosca9]

Con O(nlogn) si dimostra facilmente. Sul fatto delle costanti 'c' come faccio a sapere se nei casi induttivi sono uguali o diverse?

[hamming_burst]

"mosca9":Con O(nlogn) si dimostra facilmente.

direi che son d'accordo, per esser pignoli dovrebbe esser $O(n*\log_{3/2}(n))$

Sul fatto delle costanti 'c' come faccio a sapere se nei casi induttivi sono uguali o diverse?

bhe ci son casi particolari, ma son un po' questioni formali che alle volte si vengon tralasciate per non impazzire...

Hai introdotto un es. anche te:

"mosca9": Ho visto che a volte è possibile "far tornare" la ricorrenza sommando o sottrando dei valori all'ipotesi di partenza (ad esempio considerare cn-b con b e c da determinare nella dimostrazione) ma anche in tal caso non trovo che è O(n).

utilizzando ipotesi induttive più forti, sottraendo un bound polinomialmente inferiore, per dimotrare una tal complessità che non torna: post595334.html#p595334

es. due: post600745.html#p600745