What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
Question
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
Solution
The time complexity of the given code fragment is O(log n).
Here's why:
The loop variable 'i' is being doubled in each iteration (i = i*2). This means that the loop will run as long as 'i' is less than 'n'.
In terms of iterations, the loop will run for the number of times you can repeatedly divide 'n' by 2 until you get to 1. This is essentially the definition of log base 2 of 'n'.
Therefore, the time complexity is O(log n).
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; } }
What is the time complexity of the following code : int a = 0, i = N; while (i > 0) { a += i; i /= 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 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;}
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.