Hazem Alabiad Hazem Alabiad - 23 days ago 14
C Question

How many array access does the following code make as a function of N?

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])
count++;




A) ~3 N^2

B) ~3/2 N^2 lg N

C) ~3/2 N^3

D) ~3 N^3


Can you give an explanation for that?
And Second question, how about if k was
for(k = j+1; k < N; k++)
? Thank you ...

Answer

The first loop iterates from 0 to N-1, so it does N iterations.

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.

Comments