Paul's Python CoursePPC

Big-O, how the steps grow

Not met yet

Big-O describes how the number of steps a program takes grows as its input grows. O(1) stays the same, O(log n) adds a step each time n doubles, O(n) doubles when n doubles, and O(n²) quadruples. Only the fastest-growing part counts and constants are dropped, so 3n + 50 steps is O(n). Count the hidden loops too: in, .count() and .index() on a list each walk the whole list.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a loop inside a loop runs its body n + n times, rather than n times n.
  • Thinks the inner loop of a nested pair runs through once in total, not once for every pass of the outer loop.
  • Thinks two nested loops over the same list skip pairing an item with itself, and pairs already met.
  • Thinks a loop that halves what's left each time takes about n / 2 steps.
  • Thinks a while loop runs one more pass after its condition has become false.
  • Thinks code with one visible loop must be O(n), missing the loops hidden in `in`, `.count()` and `.index()` on a list.
  • Thinks Big-O keeps constant factors, so 3n steps is O(3n) and a different kind of growth from n.
  • Judges growth from how big one count is, rather than from how the count changes as n grows.

Where it comes up