I'm learning how to find algorithm complexity and I can't figure out what's the complexity of this algorithm. Could someone explain to me how to get the answer?
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;
}
}
Please any input is welcome. This is what I have so far:
As a is modified, you should have it in parameters of the sum:
(1) x = a - b // first iteration
(2) x = a - 2b // second iteration
(3) x = a - 3b
...
if a = k * b, the outer loop iterates k times. Hence, the final complexity is:
(a - b) + (a - 2b) + ... + (a - (k-1) b) =
(k-1) b + (k-2) b + ... + b = k * (k-1) * b/2
As you have mentioned
, time complexity is
.
a and b grow together then then ceiling remains relevant even in complexity theory).The complexity is (a^2/b)
As I described in the image, you need to sum up all "x", then you will get the complexity.
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
So in the end, if "a" and "b" were for the same order then the result is :
O(c) = 0 (c is numeric)
this means complexity is in numeric order. but if "a" was for upper order then the result is :
O((a^2)/b)
