can you help me in finding out the array access as function of N in this C code?
int i, j, k, count = 0;
for(i = 0; i < N; i++)
for(j = i+1; j < N; j++)
for(k = 1; k < N; k = k*2)
if(a[i]+a[j] >= a[k])
for(k = j+1; k < N; k++)
The first loop iterates from 0 to N-1, so it does
The second loop iterates from i+1 to N-1.
Since it is contained in the first loop it does:
N-1 + N-2 + ... + 2 + 1 iterations.
This is identical to:
N^2 / 2.
The third loop iterates from 1 to N-1, but the increment doubles every time, so it iterates
log2(N) times. And since it is contained in the first two loops, it does
log2(N) * N^2 / 2 iterations.
For each iteration the array is accessed three times.
The total amount of array accesses is:
3 * log2(N) * N^2 / 2.
To get the result if the third loop is modified, simply look at what happens to the second loop and follow all of the steps above.