What is the worst case time complexity of the following code: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));}Assume R = V.size() and C = V[0].size().
Question
What is the worst case time complexity of the following code: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));}Assume R = V.size() and C = V[0].size().
Solution
The worst case time complexity of the given code is O(2^(R+C)).
Here's the step by step explanation:
-
The function findMinPath is a recursive function, which calls itself twice in each invocation (once for the cell below the current cell and once for the cell to the right of the current cell).
-
In the worst case scenario, the function will explore all possible paths from the top-left cell to the bottom-right cell in the 2D grid.
-
The number of all possible paths in a grid of size RxC is given by the binomial coefficient (R+C choose R) which is approximately equal to 2^(R+C) for large R and C.
-
Therefore, the time complexity of the function in the worst case scenario is exponential, specifically O(2^(R+C)).
This is assuming that the function does not use any form of memoization or dynamic programming to store the results of previous function calls. If it did, the time complexity could be reduced to O(R*C).
Similar Questions
What is the worst case time complexity of the following code: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);Assume R = V.size() and C = V[0].size() and V has positive elements
What is the worst case time complexity of the following code :/* * 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);}NOTE : This question involves recursion which will be explained later in topic Backtracking. So, if you are not able to approach this question now, you can give it a try later.
What is the worst-case running time of this algorithm when the input vector nums has size 𝑛n?C++12345678910bool containsDuplicate(const std::vector<int>& nums) { std::set<int> seen; for (int x : nums) { if (seen.contains(x)) { return true; } seen.insert(x); } return false;}Θ(log𝑛)Θ(logn)Θ(𝑛2)Θ(n 2 )Θ(𝑛log𝑛)Θ(nlogn)Θ(𝑛)Θ(n)Submit
Using big-O notation in terms of its parameter n, what is the running time of the below method in its worst case? Give the tightest and simplest bound possible, and justify your answer.public static int mystery(int n) { int total = 0; for (int i = 1; i < n; i *= 2) { for (int j = i; j < 2 * i; j++) { total += j; } } return total;}
What is the time complexity of Binary Search in the worst case?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.