Skip to content
CCC Python Course

Complexity analysis and deriving the target from N

Stage
2
Module
M2.9
Lessons
1

In this module

  • Estimate how many operations a plan performs as N grows, and name that growth using Big-O.
  • Read a bound on N and judge, roughly, which complexity classes will finish in time and which will not.
  • Recognize that operation-per-second budgets and memory estimates are rules of thumb, not guarantees, and that a maximum-size test is still how you check.

Before this module

M2.5Brute force and complete search

Lessons

  1. 1Complexity analysis and deriving the target from N

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2025 J4
    Sunny Days (opens on WMOJ in a new tab) WMOJ

    Given N days of weather with exactly one day allowed to be corrected, find the longest run of sunny days that correction can produce, for N as large as 500,000.

  2. 2024 S1
    Hat Circle (opens on WMOJ in a new tab) WMOJ

    Given people seated in a circle wearing numbered hats, count how many see a matching number directly across the circle, for N as large as 1,000,000.

  3. 2019 J4
    Flipper (opens on DMOJ in a new tab) DMOJ(same problem as 2019 S1)

    Given a 2×2 grid of four numbers and a long string of flip instructions, apply every instruction in order and print the grid that results.

    Why DMOJ: A simulation problem, included here for extra practice.