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(log n)O(n^2)O(n/2)O(n^(1/2))
Question
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(log n)O(n^2)O(n/2)O(n^(1/2))
Solution
The time complexity of the given code fragment is O(log n).
Here's why:
The loop variable 'i' is being doubled at each iteration. This means that the loop will run until 'i' is greater than or equal to 'n'.
If you consider 'n' as 2^m for some m, then the loop will run for m iterations. Since m = log(n) (base 2), the time complexity of the loop is O(log n).
Therefore, the correct answer from the given choices is O(log n).
Similar Questions
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
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)
In an array-based implementation of a linear list, what is the time complexity of accessing an element at a given index?Group of answer choicesO(n)O(1)O(log n)O(n log n)
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 :int i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + 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.