What is the time complexity of the following code : int a = 0, i = N; while (i > 0) { a += i; i /= 2; }
Question
What is the time complexity of the following code : int a = 0, i = N; while (i > 0) { a += i; i /= 2; }
Solution
The time complexity of the given code is O(log N).
Here's why:
The loop in the code runs as long as 'i' is greater than 0. In each iteration, 'i' is divided by 2. This means that 'i' is halved in every step.
The number of times you can halve a number until you reach 1 (or less) is log base 2 of that number. Therefore, the loop runs for log base 2 of N times.
Hence, the time complexity of the code 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; } }
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;
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? 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)
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.