What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j < i; j++) { count += 1; } }
Question
What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j < i; j++) { count += 1; } }
Solution
The time complexity of the given code is O(N log N).
Here's why:
-
The outer loop runs log N times because i is halved in each iteration. This is a characteristic of logarithmic loops.
-
The inner loop runs i times, where i starts from N and is halved in each iteration of the outer loop. So, in the first iteration, it runs N times, in the second iteration it runs N/2 times, in the third iteration it runs N/4 times, and so on.
-
The total number of times the inner loop runs across all iterations of the outer loop is N + N/2 + N/4 + N/8 + ... This is a geometric series which sums up to 2N.
-
Therefore, the total time complexity of the code is the product of the time complexities of the outer and inner loops, which is N * log N = O(N log N).
Similar Questions
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)
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 a = 0, i = N; while (i > 0) { a += i; i /= 2; }
Q2(b) What will be the time complexity of the following? Give proper explanation. for (int j = 4; j<n; j=j+2) { val = 0; for (int i = 0; i<j; ++i) { val = val + i* j; for (int k = 0; k < n; ++k) val++; } }
What is the time, space complexity of following code :int a = 0, b = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { a = a + j; } } for (k = 0; k < N; k++) { b = b + k; }
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.