Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Constraints to Complexity
Learn/Data Structures & Algorithms/Foundations

Constraints to Complexity

6 min Beginner 7 steps

Read n from the constraints and know which algorithm will fit.

n
10^5
Budget
~10^8 ops/s
Idea
nested loops
10^X OPS8O( )1 seca machine does roughly 10^8 simple operations per second
current done skipped
In this lessonStep 1 of 7
  1. The problem
  2. Budget
  3. The table
  4. Small n
  5. Huge n
  6. O(n²) hint
  7. Recap
Step 1 / 7problem

Will nested loops pass?

The input has n = 10^5 items and your first idea is two nested loops.

That is 10^10 operations. A machine does roughly 10^8 simple operations per second, so it needs about 100 seconds.

Key idea

Estimate before you code: operations divided by 10^8 is roughly the run time in seconds.

←→ step·R replay·Space pause

You'll learn

  • Use the 10^8 operations per second budget
  • Map the input size to a target complexity
  • Recognise when exponential search is allowed
  • Treat an O(n²) idea at n = 10^5 as a hint that a pattern exists
Read the full notesDSA Pattern Playbook, 4