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

How did you get O(n^3)? As a math teacher would say, can you show you work? — John Kugelman
– John Kugelman, Commented Mar 28, 2021 at 13:32
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? — Alfodr
– Alfodr, Commented Mar 28, 2021 at 13:39

trincot · Accepted Answer · 2021-03-28 14:02:13Z

1

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.

edited Mar 28, 2021 at 14:02

answered Mar 28, 2021 at 13:53

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Best & Worst Case Algorithm Complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related