The time complexity of the following code snippet isc=0; while (n>=1) {for(i=1;i<=n;i++){ c++;}n=n/2;}
Question
The time complexity of the following code snippet is
c = 0;
while (n >= 1) {
for (i = 1; i <= n; i++) {
c++;
}
n = n / 2;
}
Solution
The given code snippet consists of a while loop and a nested for loop. The outer while loop runs as long as n is greater than or equal to 1, and in each iteration, n is halved. The inner for loop runs from 1 to n.
The time complexity of this code can be calculated as follows:
- In the first iteration of the while loop, the for loop runs n times.
- In the second iteration, n is halved, so the for loop runs n/2 times.
- In the third iteration, n is halved again, so the for loop runs n/4 times.
- This continues until n is less than 1.
So, the total number of iterations is n + n/2 + n/4 + n/8 + ... until n < 1. This is a geometric series, and the sum of this series is less than 2n.
Therefore, the time complexity of the code is O(n), where n is the initial value of n.
Similar Questions
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 :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 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)
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;}
How many times is the comparison i >= n performed in the following program?int i = 300, n = 150;main(){ while (i >= n){ i = i-2; n = n+1; }}
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.