How to make a tight O analysis of the algorithm?

Question

Make a tight big-O analysis of following code. I'm getting confused due to this array.

void main( )
    {
    int m,n,i,j,a[ ], b[ ], c[ ];
    printf(''Enter value of m and n''); 
    scanf(''%d %d'',&m, &n);
    for (i = 0; i < n; i++)
    {
      a[i] = i;
      b[i] = i*i;
      c[i]= -i;
    }

    for (j = 0; j < m; j++)
    {
      printf(''%d\t %d\t %d\n'', a(j), b(j), c(j);
    }
    }

Please explain more your difficulties, and what you've tried — malioboro, Jul 14 '17 at 08:57
Can you tell us, what you don't understand from above code & what is an issue? — sForSujit, Jul 14 '17 at 08:57

score 1 · Answer 1 · answered Jul 14 '17 at 09:17

Do find the asymptotic running time of your algorithm, it always helps to solve partial solutions.

So, you have two for-loops. They are interesting for us. How often does the first loop run? Depends on n. So the first loop must be in O(n)

Now we have a second loop. How often does this loop run? The runtime depends on m. So this loop must be in O(m), making the algorithm running in O(m+n).

The arrays itself does not affect the asymptotic running time of your algorithm.

I suggest, having a look on the following posts:

Explantions of big O

HOW-TO: Calculating Big-O

How to make a tight O analysis of the algorithm?

1 Answers1