Hazem Alabiad - 6 months ago 53

C Question

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

`for(k = j+1; k < N; k++)`

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.