Best & Worst Case Algorithm Complexity

Question

I have trouble finding the complexity of the following algorithm:

int count = 0;
for (int i = 0, i <n -1; i++) {
 for (int j = i +1; j < n; j++) {
 for (int k = n; k > n/2; k--) {
 count++;
 }
 }
}
int j = 0;
int num = count;
while(j < num) {
 for (int k = 0; k < 10; k++) {
 count++;
 }
 j++;
}

I got O(n) for the worst case. Is this right or did I mess up?

If someone could explain it would be great, maybe with what operations are happening per line. I'm getting really confused in the first part, since there are multiple nested for loops.

• John Kugelman: How did you get O(n^3)? As a math teacher would say, can you show you work?
• Alfodr: Might be because of lack of proper understanding, but it was because of the three for loops in the first block, but I wasn't too sure especially with the "for (int k = n; k > n/2; k--)", since that would seem like log(n), right or am I wrong again?

Answer 1

It is indeed O(n3).

The outer two loops give all possible ways to select two distinct values (i, j) from a set with n values. This is a triangular number and thus O(n2).

The inner loop will make n/2 iterations, which is O(n/2) = O(n), so the first block of code represents O(n3).

The second part of the code has a while loop that makes count iterations, and we know that this count is O(n3). Its inner loop iterates a constant number of times, so that represents a constant time complexity: O(Cn3) = O(n3)

And so in total we have O(n3)+O(n3) = O(n3).

As there is no variable input besides n, nor any randomness, the number of iterations is completely determined by it, and so there is no notion of best or worst. There is just a fixed time complexity.