Qual é a complexidade deste algoritmo?

Question

Estou aprendendo a encontrar a complexidade do algoritmo e não consigo descobrir qual é a complexidade desse algoritmo. Alguém poderia me explicar como obter a resposta?

void algorithm(int a, int b) {
    while (a >= b) {
        int x = a - b;
        for (int i = 0; i <= x; i++) {
            std::cout << "complexity of this algorithm?";
        }
        a = x;
    }
}

Por favor, qualquer entrada é bem-vinda. Isso é o que eu tenho até agora:

Answer 1

A complexidade é (a ^ 2 / b)

Conforme descrevi na imagem, você precisa somar todos os "x", então obterá a complexidade.

in summation part for (-b -2b -3b - ... -nb) you can write :
[![enter image description here][1]][1]-b (1+2+...)
so this is -b*(n(n+1)/2)

summation_part_definition_link

Portanto, no final, se "a" e "b" forem da mesma ordem, o resultado será:

O (c) = 0 (c é numérico)

isso significa que a complexidade está em ordem numérica. mas se "a" for para ordem superior, o resultado será:

O ((a ^ 2) / b)

Answer 2

Conforme aé modificado, você deve tê-lo nos parâmetros da soma:

(1) x = a - b  // first iteration
(2) x = a - 2b // second iteration
(3) x = a - 3b
...

se a = k * b, o loop externo itera kvezes. Portanto, a complexidade final é:

(a - b) + (a - 2b) + ... + (a - (k-1) b) = 
(k-1) b + (k-2) b + ... + b = k * (k-1) * b/2

Como você mencionou

, a complexidade do tempo é

.