Tag: time complexity

Recursion

  1. What is the worst case time complexity? 
    /* 
 * V is sorted 
 * V.size() = N
 * The function is initially called as searchNumOccurrence(V, k, 0, N-1)
 */
int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
    if (start > end) return 0;
    int mid = (start + end) / 2;
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
}
    1. O(sqrt N)
    2. O(log N)
    3. O(log^2 N )
    4. O(N)
    5. O(N * log N)
    6. O(N * sqrt N)

    Answer: O(N)

  2. What is the worst case time complexity? Assume R=V.size() and C=V[0].size() 
    int findMinPath(vector<vector<int> > V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
}
    1. O(2^(R + C))
    2. O(R*C)
    3. O(R + C)
    4. O(R*R + C*C)
    5. O(R*C*log(R*C))

    Answer: O(2^(R + C))

  3. What is the worst case time complexity, assuming R=V.size(); C=V[0].size() and V has positive elements. 
    int memo[101][101];
int findMinPath(vector<vector<int> > V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  if (memo[r][c] != -1) return memo[r][c];
  memo[r][c] =  V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
  return memo[r][c];
}

    Callsite:

    memset(memo, -1, sizeof(memo));
findMinPath(V, 0, 0);
    1. O(2^(R + C))
    2. O(R*C)
    3. O(R + C)
    4. O(R*R + C*C)
    5. O(R*C*log(R*C))

    Answer: O(R*C)

Function comparison

These are the multiple choice questions. Please, try to understand why the answer is what it is. If you are stuck, ask in the comments.

  1. Which of the following are not O(n2). Answer: n3/sqrt(n)
    1. (1510) * n + 12099
    2. n1.98
    3. n3/sqrt(n)
    4. 220 * n
  2. Sort the functions by increasing order of complexity. Answer: f3, f2, f4, f1
    1. f1(n) = 2n
    2. f2(n) = n3/2
    3. f3(n) = n log n
    4. f4(n) = nlog n
  3. Which of the following loops is the fastest? Assume the same code inside the loops. Also assume n is a positive integer. Answer: for (idx = 1; idx < n; idx *= 2)
    1. for (idx = 0; idx < n; ++idx)
    2. for (idx = 0; idx < n; idx += 2)
    3. for (idx = 1; idx < n; idx *= 2)
    4. for (idx = n; idx > -1; idx /= 2)

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)

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(N2), 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(N2), Space: O(1)