Practice question · Multiple choice
Two nested loops each running times give . Why does the analysis not simply add the two loops?
Hints
- Count the total iterations for by hand.
- Nesting and sequencing are different structures.
Show the answer
A. Because the inner loop runs in full for EACH outer iteration
Why
Nesting multiplies, sequencing adds. Two sequential -loops are ; two nested ones are , and the code looks almost identical.
Practise Complexity and efficiency basics
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Complexity and efficiency basics
- O(n²) simplifies to O(n) in Big-O notation, since constant factors are dropped.
- An O(n²) algorithm can beat an O(nlog n) one on real data. How is that consistent with the complexity classes?
- Match each everyday task to the growth rate of its work as n grows.
- An O(n²) simulation takes 2 seconds for n = 1000 particles. Predict its runtime for n = 5000, in seconds.