Algorithms / Loop Analysis
Least You Need to Know: Analyzing Loops and Nested Loops
For loop analysis, count how many times the body executes and multiply by the work per execution. Nested loops often multiply counts, while doubling or halving patterns often lead to logarithms.
جو کم از کم جاننا ضروری ہے
- A loop that performs constant work `n` times is `Θ(n)`.
- Two nested loops over ranges of size `n` often lead to `Θ(n^2)` work.
- A triangular nested loop with counts `1+2+⋯+n` is still `Θ(n^2)`.
- When a loop variable doubles or halves each time, the number of iterations is often `Θ(log n)`.
- Time complexity and extra space complexity are separate questions.
اہم علامتیں
for i in range(n)
about n iterations
∑_{i=1}^n i
triangular count
i ← 2i
doubling step
مختصر حل شدہ مثال
- A single pass over an array of length `n` with constant work per element uses `Θ(n)` time.
- A nested pass over every ordered pair of elements uses about `n^2` body executions.
- A doubling loop reaches `n` after about `log_2 n` updates.
عام غلطیاں
- Students often count the number of loops instead of the number of body executions.
- Students often forget that triangular sums are still quadratic.
- Students often mix up time cost with extra space cost.
اس قسم کے سوال کو کیسے پہچانیں
- Write down how many times the innermost body runs.
- If one loop is fully inside another, multiply the iteration counts.
- If a variable doubles each step, ask how many doublings reach `n`.
Next recommended lesson
Continue through this topic with Least You Need to Know: Modular Arithmetic, Divisibility, and Hashing Intuition.
Least You Need to Know: Modular Arithmetic, Divisibility, and Hashing IntuitionRelated lessons
Keep going with nearby lessons in the same topic.