Weierstrass ha scritto:
Se n è minore o uguale a zero, il tempo computazionale è quello di g(n)
Se n è dispari pure
Se n è pari e positivo, si continua a sottrarre -2 e fare un'operazione O(1) (la somma di h(n)) fino a quando si arriva a zero, dopodiché si ricade in g(n). Il tempo computazionale in questo caso sarè del tipo T(n) = H(n/2) + O(g(n)), e la relazione ricorsiva di H(n) è veramente semplice dato che fai 2 operazioni O(1) a ogni passaggio
Scusa, non mi è chiaro cosa intendi quando dici che ad ogni passaggio faccio due operazioni O(1); inoltre perché hai rappresentato h(n) con la H maiuscola, in che senso relazione ricorsiva?
Hai per caso usato il metodo iterativo per giungere a quella relazione (T(n) = H(n/2) + O(g(n))? Perchè io ho usato quello, mi venuta del tipo: O(g(n)) + c*(n/2), dove c sarebbe una costante che ho sostituito ad h(n) dato che è O(1). Il caso ottimo è comunque quello in cui n <=0 o dispari, mentre il pessimo quello in cui pari e maggiore di zero.
Mi è sembrato di capire che il costo rimane O(n*log(n)) sia nel caso ottimo che pessimo, puoi confermarmelo anche tu?