본문 바로가기
REC_CMPL3 What is the worst case time complexity of the following code:int memo[101][101]; int findMinPath(vector& 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]; } C.. 더보기
CHOOSE2 Which of the given options provides the increasing order of complexity of functions f1, f2, f3 and f4:f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn) f3, f2, f4, f1 f3, f2, f1, f4 f2, f3, f1, f4 f2, f3, f4, f1Good solution:n < nlog(n)n^x < n^y if x < yn^x < c^n where c is a constant (polynomials will eventually grow slower than exponentials)log(n) < nc^n < n! < n^n where c is a constant 더보기
REC_CMPL2 What is the worst case time complexity of the following code:int findMinPath(vector &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)); } Assume R = V.size() and C = V[0].size(). O(2^(R + C)) O(R*C) O(R + C) O(R*R + C*C) O(R*.. 더보기
GCD_CMPL In the following C++ function, let n >= m. int gcd(int n, int m) { if (n%m ==0) return m; if (n 0) { n = n%m; swap(n, m); } return n; } What is the time complexity of the above function assuming n > m? Θ(logn) Ω(n) Θ(loglogn) Θ(sqrt(n))Good solution:https://www.youtube.com/watch?v=pqivnzmSbq4Euclidean algorithm 더보기
CHOOSE1 CHOOSE1BookmarkSuggest EditWhich of the following is not bounded by O(n^2)? (15^10) * n + 12099 n^1.98 n^3 / (sqrt(n)) (2^20) * nGood solution:The big O gives an upper bound. It doesn’t have to be tight - just means the function won’t exceed it for n > some constant. In this case O(n^2) serves as an upper bound for a, b and d. Functions a and d are linear - more to the order of O(n). Function b .. 더보기
LOOP_CMPL2 What is the time complexity of the following code : int i, j, k = 0; for (i = n/2; i 더보기
NESTED_CMPL3 What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j 더보기

티스토리툴바