¿Qué complejidad tiene este algoritmo?

Question

Estoy aprendiendo a encontrar la complejidad de los algoritmos y no puedo entender cuál es la complejidad de este algoritmo. ¿Alguien podría explicarme cómo obtener la respuesta?

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, cualquier entrada es bienvenida. Esto es lo que tengo hasta ahora:

Answer 1

La complejidad es (a ^ 2 / b)

Como describí en la imagen, debes sumar todas las "x", luego obtendrás la complejidad.

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

Entonces, al final, si "a" y "b" fueran del mismo orden, entonces el resultado es:

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

esto significa que la complejidad está en orden numérico. pero si "a" era de orden superior, el resultado es:

O ((a ^ 2) / b)

Answer 2

Como ase modifica, debe tenerlo en parámetros de la suma:

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

si a = k * b, el ciclo exterior itera kveces. Por tanto, la complejidad final es:

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

Como ha mencionado

, la complejidad del tiempo lo es

.