Analyze While Loops and Conditional Statements Time Complexity

1. Which statement best describes why analyzing a while-loop for time complexity can be more involved than analyzing a basic for-loop?

2. A do-while loop is typically characterized by which behavior affecting its time complexity analysis?

3. If a loop body increments i each iteration and the loop condition allows i to go from 0 up to n-1, the loop body typically runs in what time complexity (order of growth)?

4. Consider a loop where a starts at 1 and repeatedly doubles (a = a * 2) until a becomes ≥ B. If B is proportional to n, the time complexity is expected to be:

5. If a loop divides a by 2 each iteration until it drops below a threshold (e.g., until it becomes 1), the number of iterations is typically:

6. A loop has the form: start with K = 1 and I = 2, repeat while K < n with updates where K increases by I and I increases by 1 each iteration. The time complexity is best described as:

7. When comparing best-case and worst-case behavior in an algorithm that includes a conditional statement around a loop, which principle is correct?

8. For translating between for-loop and while-loop, which requirement is essential for correctness of time-complexity reasoning?

9. In Euclid-style GCD computation where one variable is repeatedly reduced by subtracting the other until they become equal, what is the most appropriate overall takeaway about time complexity from the analysis perspective?

10. When analyzing loop time complexity, why do analysts often write only the “degree” (order) like Θ(n) rather than an exact formula like 3n+2?

1. A while-loop repeats its body as long as the loop ________ remains true, and stops when it becomes false.

2. A do-while loop is ________ tested, so it executes the body at least once even if the condition is initially false.

3. For a basic loop that increments from 0 to n-1, the loop body typically executes in ________ time (order of n).

4. When a value doubles each iteration (a = a * 2) until it reaches a bound proportional to n, the time complexity is ________.

5. When updates cause K to grow like accumulated increasing steps (triangular-number-like growth), the time complexity is approximately ________.