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 i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n/2; }}
The time complexity of the following code snippet isc=0; while (n>=1) {for(i=1;i<=n;i++){ c++;}n=n/2;}
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0; Group of answer choicesO(n/2)O(n^(1/2))O(n^2)O(log n)
Calculate the run-time efficiency of the following program segment:for (i = 1; i <= n; i++)printf("%d ", i);
What is the time complexity of calculating the sum of the first n natural numbers using a loop?Group of answer choicesO(n^2)O(1)O(log n)O(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.