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;}
Question
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;}
Solution
The running time of the given method in its worst case is O(n).
Here's why:
The outer loop runs log(n) times because i is doubled in each iteration. The inner loop runs i times, which is at most 2n in the last iteration.
However, the total work done by the inner loop over all iterations of the outer loop is proportional to n. This is because the sum of a geometric series 1 + 2 + 4 + 8 + ... + n is less than 2n.
Therefore, the total running time is proportional to the time spent in the inner loop, which is O(n).
Similar Questions
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
What is the time complexity of the following code? for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { System.out.println(i * j); } } a. O(n) b. O(2^n) c. O(n^2) d. O(n log n)
What is the running time of the following code?(i.e., O(?))Sum = 0;for (i=0; i<n; i++){for (j=0; j < i; j++)++sum;}
What is the time complexity of the following code :int i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n/2; }}
What will be the time complexity of the following code?int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2){ for (int j = 0; j < i; j++){ count += 1;| } }return count;
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.