Consider the pseudocode of the function given below. abc(int n)
Consider the pseudocode of the function given below.
abc(int n)
{
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}
what will the time complexity of the function abc() be?
Show answerHide answer
Correct answer: (C) O(n log n)
Explanation
The outer loop runs about n/2 times, and the inner loop doubles j, so it runs about log₂ n times. That gives O(n log n).