Loop Problems – Do the Math

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)