CODEWITHSUNDEEP
algorithmtime-complexity
Alfodr
Alfodr

Reputation: 1

Best & Worst Case Algorithm Complexity

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(𝑛) 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.

Upvotes: 0

Views: 79

Answers (1)

trincot
trincot

Reputation: 351308

It is indeed O(𝑛³).

The outer two loops give all possible ways to select two distinct values (𝑖, 𝑗) from a set with 𝑛 values. This is a triangular number and thus O(𝑛²).

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

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

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

As there is no variable input besides 𝑛, 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.

Upvotes: 1

Related Questions