1
int result = 0;
int i = 0;
while (i < n / 2){
        result += arr[i];
        i += 1;
        while (i >= n / 2 && i < n){
            result += arr[i];
            i += 1;
        }
}
printf("%d\n", result);

It seems like will be executed O(n) times because the second loop will not be executed until the first loop is executed 1/2*n times. But I can also say the first loop execute O(n) times and second one execute O(n)times so it's O(n^2). Im so confuse now, which one is correct?

UUsss
  • 25
  • 7

2 Answers2

1

The inner loop will be started only once, for the very last value of i. So you can't say "for each iteration of the outer loop, we run the inner loop". Instead, you can say, "for each iteration of the outer loop, its body runs in O(1), except for the very last iteration, when it runs in O(n)". So the total time is O(n) * O(1) + 1 * O(n) = O(n).

Also note that, if something runs in O(n), it is not exactly wrong to say it also runs in O(n^2). The O(n) is just the tighter bound, and usually, you are expected to get the tightest possible upper bound.

Gassa
  • 8,546
  • 3
  • 29
  • 49
1

One way to look at this is to realise that result += arr[i]; will be executed exactly once for every value of i between 0 and n-1. So, although the code looks confusing, it is O(n).

trincot
  • 317,000
  • 35
  • 244
  • 286