What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2)          a[i]=0; Group of answer choicesO(n/2)O(n^(1/2))O(n^2)O(log n)

Break Down the Problem

1. The code fragment consists of a loop that starts at 1 and doubles i each time, continuing as long as i < n.
2. We need to analyze how many times the loop executes based on the value of n.

Relevant Concepts

3. We are looking for the time complexity, which is typically expressed in Big O notation. For this code fragment, we want to understand how many iterations the loop executes as a function of n.

Analysis and Detail

4. On each iteration, i is multiplied by 2, which forms a geometric progression:

   • 1st iteration: $i = 1$
   • 2nd iteration: $i = 2$
   • 3rd iteration: $i = 4$
   • 4th iteration: $i = 8$
   • ...
   • The loop continues until $i$ reaches or exceeds $n$.

5. The condition for the termination of the loop can be expressed as: $2^k < n$ where $k$ is the number of iterations. Taking logarithm base 2 of both sides: $k < \log_2(n)$ Therefore, the loop executes approximately $\lfloor \log_2(n) \rfloor$ times.

Verify and Summarize

6. Given the numbers of iterations calculated as $\lfloor \log_2(n) \rfloor$, we can conclude that the time complexity of the provided code fragment is $O(\log n)$.

Final Answer

The time complexity of the code fragment is $O(\log n)$.