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.
Question
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.
Solution
The worst case time complexity of the given code is O(N).
Here's the step by step explanation:
-
The function searchNumOccurrence is a recursive function that is searching for the number of occurrences of a number 'k' in a sorted vector 'V'.
-
In the worst case scenario, the number 'k' could be repeated in the entire array.
-
In such a case, the function would be called for each element of the array once.
-
Since the size of the array is 'N', the function would be called 'N' times.
-
Therefore, the worst case time complexity of the function is O(N).
Note: The time complexity is not log(N) because in the worst case, the function does not divide the problem into half at each step (which is what happens in binary search). Instead, it could potentially process each element of the array once, leading to a linear time complexity.
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 time complexity (worst case) of a binary search in an array of size n?
Which of the following operations has the WORST time complexity for an array of N elements? Accessing an element by index. Inserting an element at the beginning. Deleting an element from the middle. Searching for an element using linear search.
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 the Quick Sort algorithm in the worst case? Question 20Select one: O(n^2) O(n) O(n log n) O(2^n)
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.