[Complessità algoritmica] Correzioni e calcolo sommatoria

[probid]

Salve,
ho qualche problemino con il calcolo della complessità degli algoritmi. Ho provato a svolgere un esercizio del quale riporto il procedimento che ho seguito e di cui mi manca il passo finale.
Vi sarei molto grado se mi aiutaste a capire se sbaglio qualcosa (sicuramente! ) e dove (procedimenti, simbolismo...).

La funzione di cui devo calcolare l'ordine di grandezza è questa:

function f ( n : int ) -> int
   a = 0
   for i = 1 to n
      for j = 1 to n
         for k = 1 to i
              for w = 1 to j
                  a++
   if n > 10
       return 2 * f ( n - 5 ) + a
   else
       return 100

Inizio a trovare il costo della parte iterativa prima dell'if:

$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{i}\sum_{w=1}^{j}O(1) = \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{i} j=\sum_{i=1}^{n}\sum_{j=1}^{n}ij=\sum_{i=1}^{n}i\sum_{j=1}^{n}j=\sum_{i=1}^{n}i\frac{n(n+1)}{2} =$

$\frac{n(n+1)}{2}\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \frac{n(n+1)}{2} = \frac{n^2(n^2+2n+1)}{4} = \frac{n^4+2n^3+n^2}{4} \in \Theta (n^4)$

Ora, per la ricorsione, ho l'equazione di ricorrenza:

$T(n) = {(T(n-5) + \Theta(n^4)\, n>10),(\Theta(n^4)\, n \leq 10):}$

Uso l'albero di ricorsione e trovo che ad ogni profondità i ho un nodo che costa $c(n-5i)^4$ e il problema ha dimensione $n-5i$, che diventa $\leq10$ (arrivo al caso base) quando $i \geq (n - 10)/5 = n/5-2$.
Ci sono quindi $n/5-2$ livelli più il finale (quando arrivo al caso base della ricorsione):
$T(n) = \sum_{i=0}^{n/5-2}c(n-5i)^4 + Theta(n^4)$

A questo punto, sperando che finora non sia tutto completamente errato non so come procedere per limitare (?) la sommatoria.

Grazie mille in anticipo a chi mi aiuterà

[hamming_burst]

Ciao,
prima di tutto, grazie per la corretta impostazione dei tag e della formule.

Inizio a trovare il costo della parte iterativa prima dell'if:

$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{i}\sum_{w=1}^{j}O(1) = \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{i} j=\sum_{i=1}^{n}\sum_{j=1}^{n}ij=\sum_{i=1}^{n}i\sum_{j=1}^{n}j=\sum_{i=1}^{n}i\frac{n(n+1)}{2} =$
$\frac{n(n+1)}{2}\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \frac{n(n+1)}{2} = \frac{n^2(n^2+2n+1)}{4} = \frac{n^4+2n^3+n^2}{4} \in \Theta (n^4)$

ok

Ora, per la ricorsione, ho l'equazione di ricorrenza:

$T(n) = {(T(n-5) + \Theta(n^4)\, n>10),(\Theta(n^4)\, n \leq 10):}$

ok

Uso l'albero di ricorsione e trovo che ad ogni profondità i ho un nodo che costa $c(n-5i)^4$

mmm l'albero è un po' incasinato in questo caso, ma proviamo a venirne fuori.
La ricorsione è corretta, ma manca di contare la costante nella ricorsione:

$n\ ->\ c(n-5)^4\ ->\ 2*c(n-5*2)^4\ ->\ ...\ ->\ i*c(n-5*i)^4$

e il problema ha dimensione $n-5i$, che diventa $\leq10$ (arrivo al caso base) quando $i \geq (n - 10)/5 = n/5-2$.
Ci sono quindi $n/5-2$ livelli più il finale (quando arrivo al caso base della ricorsione):

dovrebbe essere corretto (anche se mi pare si possa fare in modo più semplice in questo caso particolare, con un solo cammino radice-foglia).

Perciò la sommatoria diviene:
$ \sum_{i=0}^{n/5-2}i*c(n-5i)^4$

Per calcolarsi una limitazione con queste schifezzuole di sommatorie, si deve un po' capire chi domina il tutto.
Prima srotoliamo la potenza:

$ \sum_{i=0}^{n/5-2}i*c(n-5i)^4 = c\sum_{i=0}^{n/5-2}i(625i^4 - 500i^3n + 150i^2n^2 - 20 i n^3 + n^4) =$

non serve calcolarci nulla di preciso, ci serve una limitazione. elimini tutte le costanti e moltiplichi $i$ per il resto della parentesi:

$\sum_{i=0}^{n/5-2}i^5 \approx n^6$
$- n\sum_{i=0}^{n/5-2}i^4 \approx n^6$
$ +n^2\sum_{i=0}^{n/5-2}i^3 \approx n^6$
$- n^3\sum_{i=0}^{n/5-2}i^2 \approx n^6$
$+ \sum_{i=0}^{n/5-2}n^4 \approx n^5$.

le sottrazioni possiamo "eliminarle" per le proprietà delle complessità asintotiche, anche se matematicamente non è ovviamente possibile. Ma questo trucco ci fa capire che una limitazione superiore è $O(n^6)$.

Ora si devono calcolare le foglie nel caso base, perciò quando $n=10$:

$c*n/5-2*O(n^4) \in O(n^5)$

ora si sceglie quale delle due complessità domina tutto e si comprende è $O(n^6)$

Se hai dubbi scrivi senza problemi, utilizzando l'albero in questi casi è facile sbagliarsi.

NB: il discorso delle foglie, molti docenti lo lasciano un po' da parte, ed il caso base nell'albero è delicato. Perciò prova a leggere anche questa discussione che penso chiarisca alcuni punti oscuri: post594512.html#p594512 vedi dove c'è il disegno.

[probid]

"hamming_burst":
mmm l'albero è un po' incasinato in questo caso, ma proviamo a venirne fuori.
La ricorsione è corretta, ma manca di contare la costante nella ricorsione:

$n\ ->\ c(n-5)^4\ ->\ 2*c(n-5*2)^4\ ->\ ...\ ->\ i*c(n-5*i)^4$

Quale metodo altrimenti? Non si può applicare il master theorem, nè riuscirei a formulare una soluzione da provare per sostituzione.
Riguardo la costante: è solo un formalismo perché a livello di calcolo non cambia nulla, vero?
Sul Cormen & Co. mi pare consideri $c$ indipendentemente dal livello.

$\sum_{i=0}^{n/5-2}i^5 \approx n^6$
$- n\sum_{i=0}^{n/5-2}i^4 \approx n^6$
$ +n^2\sum_{i=0}^{n/5-2}i^3 \approx n^6$
$- n^3\sum_{i=0}^{n/5-2}i^2 \approx n^6$
$+ \sum_{i=0}^{n/5-2}n^4 \approx n^5$.

Ho capito come sono ottenute le sommatorie, ma non l'approssimazione.
Avevo pensato che poiché il termine massimo limita gli altri, per esempio l'ultima diventa:
$\sum_{i=0}^{n/5-2}n^4 \leq \sum_{i=0}^{n/5-2}(n/2-2)^4 = (n/2-2)(n/2-2)^4 \in O(n^5)$.

È corretto?

Grazie!