Calcolo della complessità

[Perfo]

Ciao a tutti
Dovrei calcolare la complessità di un algoritmo in java.
Praticamente ho fatto il calcolo ma ho grossi dubbi in queste porzioni di codice:

 
while (testa != coda) {              
for (t = coda; t != null && t.struttura.frequenza > agg; t = t.prec);
}

Qui il dubbio è quante volte iterano il ciclo while e quello for, dato che non è determinabile con un numero....

void trasforma(Nodo p) { 
if (p.sx == null && p.dx == null){
        	p.dx = stream[p.segno+128];        
        	stream[p.segno+128] = p;
        }					 	       	
        else {                                     	 
             trasforma(p.sx);  	
             trasforma(p.dx); 	
        }                                          	
}

Qui invece quante volte viene chiamata la ricorsione?

Aiutatemi se potete, vi ringrazio già da ora

[jappilas]

l' algoritmo su cosa opera? su una lista ?
in ogni caso , a meno che non entri in ciclo infinito per aver omesso/errato qualche verifica di condizione, si eseguirà la trasforma sugli elementi dello stream che sono per definizione, finiti (è un numero finito la dimensione della memoria, è un numero finito la banda eventuale di trasmissione dello stream, è un numero finito, il tempo che vivi davanti allo schermo per ricevere pacchetti dello stream, nel caso questo appaia come un "continous feed".. )

il caso estremo (numero di operazioni nel caso peggiore) dovrebbe essere, data una finestra di N elementi,
<n. di operazioni della transform> x N x (N-1)
nel caso la transform chiami se stessa altre n-1 volte , per ogni elemento dello stream contenuto nella finestra
che , visto che il primo termine è una costante e N-1 (circa) N, non vorrei sbagliare ma mi sembra diventi O(N^2)

[franksisca]

per il doppio ciclo innestato quoto O(n^2), mentre per la ricorsione attento alla dimensione dell'input

[Perfo]

Ciao a tutti

Grazie Mille

Cmq l'alg opera su una lista con la quale implemento un albero binario.

Il codice che è contenuto in "while testa != coda" serve per raggruppare tanti nodi in un unico albero.
posto il codice completo del ciclo

while (testa != coda) {                  			
            agg = testa.struttura.frequenza + testa.succ.struttura.frequenza;
            for (t = coda; t != null && t.struttura.frequenza > agg; t = t.prec);
            y = new NodoP(t,t.succ);					
            t.succ = y;							
            if (t == coda)   coda = y;
            else y.succ.prec = y;	
            y.struttura = new Nodo((byte)0,agg,0,testa.struttura,testa.succ.struttura);
            testa = testa.succ.succ;					
            testa.prec = null;						
        }

in pratica a ogni iterazione toglie 2 nodi raggruppandoli in un minialbero la cui radice viene concatenata nella lista. quindi con N elementi devo iterare N-1 volte credo....
Il ciclo for interno fa ogni volta una ricerca partendo dall'ultimo nodo della lista e andando all'indietro. In teoria considerando il caso peggiore il suo costo è n?
Quindi il totale sarebbe O(N-1)*(N + spiccioli) cioè anche qui O(N^2)?

La trasforma dovrebbe eseguire tutte le sue operazioni solo per i nodi terminali, diciamo N; mentre per gli altri chiama la ricorsione e in teoria dovrebbero essere N-1 quindi non so se è O(N^2) oppure O(N+(N-1))=O(2N)=O(N)

????

Grazie ancora a tutti