Complessità algoritmo

[fra84fra84]

Ciao a tutti...
ho il seguente algoritmo di cui dovrei calcolare la complessità:

int n=2^k;
for(int i=1;i<=n;i++){
j=2;
while(j<=n){
j=j^2;
}//while
}//for

non è O(n logn) perchè se ipotizzo k=5 allora il for esterno sarebbe eseguito 32 volte ed il while 3 volte(j=2,4,16,STOP), quindi avrei un costo pari a 32*3=96...e O(nlogn)=32*5=180....
non è O(n^2).....
aiuto!!!

[onlyReferee]

Ciao anastasi.fr
Facendo delle rapide considerazioni secondo me la complessità è $O(n k)$. Ora sono un po' di fretta ma nel pomeriggio appena ho un attimo di tempo ti scrivo per bene il perché.
---------
Edit, 12/09/14 h 18.33

Come promesso eccomi a spiegare quella che presumibilmente è (secondo me) la complessità dell'algoritmo dato.
La parte che merita più attenzione è chiaramente quella del while più interno. Lo stesso termina nel momento in cui si ha $j > n$, ossia $j > 2^k$ (per come è definito $n$). Risolvendo tale semplice disequazione esponenziale si ha:
\[
j > 2^k\\
2^{\log_2 j} > 2^k\\
k < \log_2 j
\]
Questo significa implicitamente che il controllo presente nel ciclo while viene eseguito $k$ volte (e di conseguenza l'istruzione di aggiornamento di $j$ al suo interno $k - 1$). Essendo pertanto il controllo presente nel for eseguito un totale di $n + 1$ volte ecco che la complessità totale dell'algoritmo è $O(nk)$.