[Algoritmi] Ricorrenza con metodo sostituzione

[mosca9]

Salve a tutti, ho un problema con questa ricorrenza un pò strana:

$T(n)=\{(1, n=1), (3\sum_{i=1}^k T(n_i) , n>1):}$

so che $\sum_{i=1}^k n_i<=n$ e che $n_i<=n/2$ per i=1,2,....k. Devo mostrare che è $T(n)=O(n*3^(log_2n))$

Dovendo usare il metodo di sostituzione non riesco a trovare un passo induttivo adatto da utilizzare per la dimostrazione. Quella sommatoria mi sta facendo penare non poco. Spero che qualcuno riesca ad aiutarmi.

[totissimus]

Per ogni \( n \) risulta : \( T(n) \leq n3^{log_2 n}\). Procediamo per induzione:

1) base: per \( n= 1 \) la disuguaglianza è ovviamente vera;

2) supponiamo vera la disuguaglinza per tutti gli \( i
3) proviamo la disuguaglinaza per \( n\) :

\( T(n) = 3\sum_{i=1}^k T(n_i )\leq3 \sum_{i=1}^k n_i 3^{log_2 n_i} \leq 3 3^{log_2 {(\frac{n}{2})}} \sum_{i=1}^k n_i\)

\( \leq 3n 3^{log_2(\frac{n}{2})}= n 3^{log_2 n}\).

Mi pare che abbiamo finito.