[Analisi Algoritmi] Equazione di ricorrenza

[hamming_burst]

Ripropongo due esercizi esposti a degli esami di un corso di Algoritmi e strutture dati, a cui uno di questi mi fece perdere parecchio tempo (inutilmente) per dimostrarne la limitazione asintotica.

1. Sia data la seguente equazione di ricorrenza

$T(n) = {(1 if n=1),(T(n/2) + 1 if n>1\ is\ even),(T(n-2) + 1 if n>1\ is\ odd):}$

trovare limite inferiore ($Omega()$) e superiore ($O()$).
suggerimento: utilizzare il Master Theorem o i teoremi elementari per trovare una stima, ma bisogna dimostrare con induzione (metodo della sostituzione) se tali limitazioni sono vere.

2. Sia data la seguente equazione di ricorrenza

$T(n) = {(k if n<=2),(2T(n/4) + log(n) if n>2):}$

trovare limite inferiore ($Omega()$) e superiore ($O()$).
suggerimento: uguale di sopra.

Se volete provare

[robbstark1]

A occhio direi che $[log_{2} n]+1 <= T(n) <= [n/2]+1$.

[hamming_burst]

"robbstark":A occhio direi che $[log_{2} n]+1 <= T(n) <= [n/2]+1$.

Per la 1. ok
Ora come lo dimostri

[robbstark1]

Per $n$ dispari $T(n)=(n+1)/2$: vale per $n=1$, se vale per $n$ vale per $n+2$, infatti $T(n+2)=(n+1)/2+1=((n+2)+1)/2$. Questo coincide con il bound superiore che ho dato (anche se non ho ancora dimostrato che effettivamente lo è).
I numeri pari sono in generale della forma $n=2^m*p$, con $m$ naturale e $p$ naturale dispari. Per induzione si dimostra che $T(2^m*p)=T(p)+p$, che, col risultato dimostrato per i dispari, dà $T(2^m*p)=(p+1)/2+m<=(2^m*p+1)/2$. Quest'ultima disuguaglianza si dimostra con qualche passaggio, vedendo che è equivalente a $p+2m<=2^m*p$. Così è dimostrato il bound superiore.
Per quello inferiore basta osservare che vale ovviamente per tutti i termini di posto dispari, mentre per quelli di posto pari $log_{2}(2^m*p)=m+log_{2}p<=[log_{2}n]+1<=(p+1)/2+m$, almeno asintoticamente, ma mi pare che sia valido in generale. Si può anche verificare per induzione che la sottosuccessione delle potenze di $2$ eguaglia esattamente il bound inferiore.