1.5.3 Time Complexity of While and if #3

Analyzing while Loops and Conditional Statements

A loop’s time complexity depends on how its condition and updates behave—not simply on whether it is written as a while or for loop. To analyze a loop, trace how its variables change, determine when the condition becomes false, and count the iterations required.

Loop Types and Behavior

• A conventional for loop whose variable increases or decreases by a fixed amount often runs a predictable number of times, such as (n).
• A while loop continues as long as its condition is true. Its iteration count must be worked out from the condition and updates; it cannot be inferred from the syntax alone.
• A while loop checks its condition before each iteration, so its body may run zero times.
• A do-while loop checks its condition after the body, so the body runs at least once.
• Older loop forms include:
  • A Pascal-style for loop, which can specify a step size, such as increasing by 2.
  • A repeat-until loop, which continues while its stopping condition is false and stops when that condition becomes true.
• In C, many loops written with while can also be expressed with for. However, C’s for loop allows flexible initialization, condition, and update expressions, so it must still be analyzed rather than assumed to run in (O(n)).

Examples and Complexities

• Linear increment: A counter starts at 0 and increases by 1 until it reaches (n). The body runs (n) times, and the condition is checked once more to detect termination. The total complexity is (O(n)).
• Doubling: A variable starts at 1 and doubles each iteration until it reaches a bound (B). After (k) iterations, it is approximately (2^k), so (k) is approximately (\log_2 B). If the bound is treated as (n), the complexity is (O(\log n)).
• Halving: A variable starts at (n) and is divided by 2 each iteration until it is small. This takes approximately (\log_2 n) iterations, giving (O(\log n)) complexity.
• Growing by a counter: A counter (i) increases by 1 while another variable (K) accumulates the values of (i). After (m) iterations, (K) grows roughly like (1 + 2 + \cdots + m), or (m^2/2). Reaching a threshold (n) therefore takes approximately (\sqrt{n}) iterations, giving (O(\sqrt{n})) complexity.
• Subtraction-based GCD procedure: The algorithm repeatedly subtracts the smaller of two values from the larger until they are equal. The iteration count depends on the inputs. The video gives a worst-case bound of (O(n)) in terms of the input magnitude and a constant-time best case. If the values are already equal, the loop body does not run, though the algorithm still performs a constant amount of checking.

Conditional Statements and Cases

An if statement can lead to different amounts of work depending on which branch runs. In the example, one branch performs a constant-time action, while another runs a loop (n) times. These branches have (O(1)) and (O(n)) behavior, respectively, so the algorithm’s best- and worst-case complexities can differ.

The presence of an if statement does not automatically mean an algorithm has different best- and worst-case complexities. Examine the work performed by each branch and which inputs select it.

General Analysis Method

1. Identify each loop’s condition and update.
2. Trace the changing variables, or express their values after (k) iterations.
3. Determine how many iterations are needed for the condition to become false.
4. Count the work per iteration and, when relevant, the final condition check.
5. For conditionals, analyze the work in each possible branch and distinguish best-case from worst-case behavior when appropriate.
6. Express the result using asymptotic notation, ignoring constant factors and lower-order terms.

Speakers and Sources

• Instructor/narrator: Abdul Bari, the sole identifiable speaker in the subtitles.
• Other speakers or sources: None identifiable.