Originariamente inviato da Fla@sh_b
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?


direi perfetto!
ciao