Ciao marco_c ! Ti ringrazio per la risposta...forse è la volta buona che capisco per bene come calcolare la complessità di una funzione!
Il procedimento che segue è valido?
codice:
Posto k il numero di iterazioni del quale voglio stabilire una stima della complessità in funzione di n
potrei sfruttare qualcosa del genere:
::: CICLO WHILE :::
k=1 --- prima iterazione --- j=2
k=2 --- sec. iterazione --- j=4
k=3 --- terza iterazione --- j=8
k=4 --- quarta iterazione --- j=16
k --- ultima iterazione --- j=2^k;
Alla k-esima iterazione j=2^k=n; -> 2^k=n -> k=log_base2_n!
::: CICLO FOR :::
k=1 --- prima iterazione --- j=2
k=2 --- sec. iterazione --- j=4
k=3 --- terza iterazione --- j=6
k=4 --- quarta iterazione --- j=8
k --- ultima iterazione --- j=2*k;
Alla k-esima iterazione j=2*k=n; -> 2*k=n -> k=n/2!
::: COMPLESSITA DI F() :::
O(log_base2_n * n/2) = O(nlog_base2_n)
Che ne pensate? E' corretto?