Hazem Alabiad - 1 year ago 90
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 ...

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download