Question

Consider the following C-program fragment in which i, j, and n are integer variables. for (i = n, j = 0; i > 0; i / = 2, j + = I);
Let Val (j) = denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

• A. val (j) = $\ominus$ ($\sqrt{n}$)
• B. val (j) = $\ominus$ (n log n)
• C. val (j) = $\ominus$ (log n)
• D. val (j) = $\ominus$ (n)

Answer 1

The correct option is D val (j) = $\ominus$ (n)

The frequency of the loop is i = i/2 = n/2 so after termination of for loop vol(j) = O(n) on average.

j = n + $\frac{n}{2}$ + $\frac{n}{2^2}$ + $\frac{n}{2^{lo{g}_{2}n}}$ = $\ominus$(n)