Consider the program void function(int n) { int i, j, count=0; for (i=n/2; i…
2017
Consider the program
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}The complexity of the program is
- A.
O(log n)
- B.
O(n2)
- C.
O(n2 log n)
- D.
O(n log n)
Attempted by 166 students.
Show answer & explanation
Correct answer: D
The outer loop iterates from n/2 to n, resulting in approximately n/2 iterations, which simplifies to O(n).
The inner loop doubles j until it exceeds n, resulting in log base 2 of n iterations, or O(log n).
Multiplying these complexities gives a total time complexity of O(n log n).