COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
int i, j, k = 0; for (i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; } }
|
|
O(n)
|
|
|
O(nLogn)
|
|
|
O(n^2)
|
|
|
O(n^2Logn)
|
Explanation:
Detailed explanation-1: -for (j=2; j<=n; j=j*2) // This inner loop will run ( log2n) times. k = k + n/2; //Final value k will be × log2n times i.e. n 2 4 log2n. This function will have time complexity O(n2log2n). Hence the correct answer is “option 2”.
Detailed explanation-2: -Hence, time complexity will be O(n log n).
Detailed explanation-3: -For example, if you had another for i=1 to n loop inside the for i=1 to 2n loop, the time complexity would be O(n^2).
There is 1 question to complete.