Loop Problems – The basics

Identify the space and time complexity of the following chunks of code. I will post the answers later

1. Simple loop

   int a = 0, b = 0;
   for (i = 0; i < N; i++) {
       a = a + rand();
   }
   for (j = 0; j < M; j++) {
       b = b + rand();
   }
   

   Select here to see the answer: Time: O(N+M), Space: O(1)

2. Nested loop

   int a = 0, b = 0;
   for (i = 0; i < N; i++) {
       for (j = 0; j < N; j++) {
           a = a + j;
       }
   }
   for (k = 0; k < N; k++) {
       b = b + k;
   }
   

   Select here to see the answer: Time: O(N²), Space: O(1)

3. Another nested loop

   int a = 0;
   for (i = 0; i < N; i++) {
       for (j = N; j > i; j--) {
           a = a + i + j;
       }
   }
   

   Select here to see the answer: Time: O(N²), Space: O(1)