Как рассчитать асимптотическое время выполнения степени числа при повторном сложении?

Question

function calculatePower(k,n) {
var power = 1;
for(var i =0;i<n;i++) {
    var tempPower = 0;
    for(var j=0; j<k;j++) {
        for(var q=0; q<power; q++) {
            tempPower++;
        }
    }
    power = tempPower;
}
return power;
}
calculatePower(2,3);

Как бы я рассчитал время работы для чего-то подобного? Будет ли это что-то в строках O (k + k ^ 2 + .... + k ^ n) или O (k ^ n)?

Answer 1

Поскольку tempPower будет инициироваться на 0 в каждой итерации в течение i, оно будет равно k*power для каждой итерации. Следовательно, power = k*power и временная сложность кода будут T(k,n) = k + k^2 + k^3 + ... + k^n = k^{n+1} - 2 = Theta(k^{n+1}).