Zaf's sharings

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

1. While loop

   int a = 0, i = N;
   while (i > 0) {
       a += i;
       i /= 2;
   }
   

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

2. Nested loop

   int count = 0;
   for (int i = N; i > 0; i /= 2) {
       for (int j = 0; j < i; j++) {
           count += 1;
       }
   }
   

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

3. Theta maybe?

       int i, j, k = 0;
       for (i  = n/2; i <= n; i++) {
           for (j = 2; j <= n; j = j * 2) {
               k = k + n/2;
           }
       }
   

   Select here to see the answer: Time: Θ(n logn), Space: O(1)

4. GCD

       int gcd(int n, int m) {
               if (n%m ==0) return m;
               if (n < m) swap(n, m);
               while (m > 0) {
                   n = n%m;
                   swap(n, m);
               }
               return n;
       }
   

   Assume n > m
   Select here to see the answer: Time: Θ(log n), Space: O(1)

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)