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;}
Question
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;}
Solution
The running time of the given code is O(n^2).
Here's why:
The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs i times. In the worst-case scenario, i is equal to n. Therefore, the total number of operations is the sum of the first n integers, which is (n*(n+1))/2.
This simplifies to 0.5n^2 + 0.5n. In Big O notation, we only care about the highest order term and ignore constants, so the running time is O(n^2).
Similar Questions
What is the time complexity of the following code : int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } }
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 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 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.