Big-O für While-Schleifen mit Benutzereingabe

Question

Angenommen, Modul X benötigt p Zeiteinheiten zur Ausführung, wobei p eine Konstante ist. Finden Sie die Komplexität jedes der folgenden Algorithmen, wobei n die Größe der Eingabedaten und q eine positive ganze Zahl größer als 1 ist. Wie groß ist die zeitliche Komplexität?

set i = 1 
    `while i ≤ n` 
     `Module X` 
     `i = q * i` 
    endwhile 

Answer 1

log(n), wo die Basis der logarithmischen Funktion q ist.

Hinweis: i steigt exponentiell an.