Computer Science I / Complexity and Performance Trade-offs
Practice question · True or false

Big-O notation compares how algorithms scale, so an O(nlogn)O(n\log n) algorithm always runs faster than an O(n2)O(n^{2}) one on the same input.

Hints
  1. Ask what big-O deliberately throws away.
  2. Constant factors and the size of n both survive in the real runtime.
Show the answer

False

Why

False. Big-O describes growth as n tends to infinity and discards constant factors, so a heavily-optimised O(n2)O(n^{2}) routine can beat a constant-heavy O(nlogn)O(n\log n) one at every n a real program ever sees. The crossover point is a measurement, not something the notation tells you.

Read the lesson: Complexity and Performance Trade-offs →

Practise Complexity and Performance Trade-offs

The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.

More questions on Complexity and Performance Trade-offs