- 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); }
O(sqrt N)
O(log N)
O(log^2 N )
O(N)
O(N * log N)
O(N * sqrt N)
Answer:
O(N)
- What is the worst case time complexity? Assume
R=V.size()
andC=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)); }
O(2^(R + C))
O(R*C)
O(R + C)
O(R*R + C*C)
O(R*C*log(R*C))
Answer:
O(2^(R + C))
- What is the worst case time complexity, assuming
R=V.size(); C=V[0].size()
andV
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);
O(2^(R + C))
O(R*C)
O(R + C)
O(R*R + C*C)
O(R*C*log(R*C))
Answer:
O(R*C)