complexity-theory - 证明这个双循环的时间复杂度是 O(n)

Question

你如何证明整个循环序列是 O(n)？还是 O(n)？乍一看，只看双循环可能会认为它是 O(n^2) 但我不认为它是......

int i = 0;
int arr[N];
int idx = 0;
for (i = 0; i < 2; i++)
{
    for (j = 0; j < N/2; j++)
    {
      idx = (i * N/2) + j;
      foo(arr[idx]);
    }
 }

Answer 1

The outer loop is constant, so the loop is the same as doing:

for (j = 0; j < N/2; j++)
{
  idx = (0 * N/2) + j;
  foo(arr[idx]);
  idx = (1 * N/2) + j;
  foo(arr[idx]);
}

Which actually makes the intent of the code a lot clearer also, but as you can see, the amount of operations scales linearly with N, so it's O(N) complexity rather than exponential growth. I can't explain it any better as it's 8.30am and I haven't slept, but I imagine you get my gist.