[Algoritmi] calcolo tempo di esecuzione funzione

[jigen45]

Ciao ragazzi, può sembrare stupido ma non sono sicuro su un calcolo da fare:
La funzione è:

fun(intero k) {
    i=0
    a=1
    while (a<=k) {
        for b=1 to a do i++
        a=2*a
    }
}

Allora io ho fatto così: nel ciclo esterno il tempo è $ O(lg k) $, ma quello interno non sono sicuro se è $ O(2^k) $ o se bisogna scrivere una sommatoria... Mi potete dare una mano? Grazie

[el_brando]

Allora, effettivamente il ciclo esterno si ripete \( \lceil \log_2k \rceil \) volte mentre quello interno diciamo che calcola in $ i $ la progressiva potenza di $ 2 $... Sostanzialmente questa funzione calcola (in $ i $) la somma delle prime \( \lceil \log_2k \rceil \) potenze di $ 2 $ quindi il valore di $ i $ a fine chiamata sarà pari a \( \sum_{j = 0}^{\lfloor \log_2k \rfloor} 2^j \)...
Quella serie geometrica si approssima con \( 2^{\lfloor \log_2k \rfloor + 1}-1 \) quindi la funzione ha complessità in tempo \( O(2^{\log_2k}) \)...

[jigen45]

quindi posso concludere che la funzione ha tempo lineare?..