1.5.2 Time Complexity Example #2

Main Ideas

The video explains how to analyze loop time complexity by tracking how a loop variable changes and determining how many updates it takes to reach the stopping condition. The key distinction is whether the variable changes by a constant amount or by a constant factor.

Loop Patterns and Their Complexity

• Incrementing or decrementing by a constant

  • Examples include i++, i += 2, or decreasing from n by 1.
  • The loop runs a number of iterations proportional to n, so its time complexity is Θ(n).
  • Changing the step from 1 to 2, 10, or another fixed constant changes the iteration count only by a constant factor, not the asymptotic complexity.

• Multiplying the loop variable by a constant

  • A loop that starts at 1 and doubles each time visits values such as 1, 2, 4, 8, ....
  • After k updates, the value is 2^k. Setting this near n gives k ≈ log₂ n.
  • The loop therefore takes Θ(log n) time. Multiplying by 3 instead gives Θ(log₃ n); the base does not affect the asymptotic class.
  • For a loop with condition i < n, the exact number of executions is ceil(log₂ n) for positive integer n > 1. For example, it runs 3 times when n = 8 and 4 times when n = 10.

• Dividing the loop variable by a constant

  • Starting at n and halving repeatedly gives values such as n, n/2, n/4, ....
  • The number of divisions needed to reach a value below 1 is logarithmic, so the loop takes Θ(log n) time.

• A loop bounded by a square

  • If a loop continues while i * i <= n and i increases by 1, it stops when i is around √n.
  • It therefore takes Θ(√n) time.

Independent and Nested Loops

• Independent loops run one after another: add their costs. Two separate linear loops take n + n = 2n operations, which simplifies to Θ(n), not Θ(n²).
• Nested loops: multiply their iteration counts. An outer loop that runs n times with an inner loop that doubles its counter and runs Θ(log n) times takes Θ(n log n) overall.

Using a Variable from an Earlier Loop

The video also considers a loop whose limit is a value p produced by a previous loop. If the first loop makes p proportional to log n, and a later loop doubles its counter until it reaches p, then the later loop takes Θ(log p) = Θ(log log n) time.

General Method

1. Write down the loop variable’s values across iterations.
2. Express its value after k iterations:
   • Constant increments typically produce a linear relationship.
   • Multiplication or division by a constant produces a power relationship.
3. Use the stopping condition to solve for k, the number of iterations.
4. For multiple loops, add costs for sequential independent loops and multiply costs for nested loops.
5. Simplify the result using asymptotic notation, dropping constant factors and lower-order terms. Exact counts may require a floor or ceiling, but that distinction does not change the asymptotic class.

Speaker or Source Featured

• Abdul Bari — instructor/presenter, as attributed to the channel.