Recursion

/* 
 * 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)

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))

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)