If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Categorizing run time efficiency

AP.CSP: AAP‑4 (EU), AAP‑4.A (LO), AAP‑4.A.3 (EK), AAP‑4.A.4 (EK), AAP‑4.A.7 (EK)

Problem

Meredith implements a "graph coloring" algorithm, which comes up with colors for graph vertices such that no neighboring vertices share the same color.
The algorithm outputs graph colorings like this one:
Using a palette of just 3 colors, she runs the algorithm on graphs with varying amounts of vertices and records how long it takes.
Her findings are summarized in this table:
Graph verticesSteps
481
6729
86561
Based on the table, which of the following statements describe the run time for this algorithm?
👁️Note that there are 2 answers to this question.
Choose 2 answers:
Choose 2 answers:
Stuck?
Stuck?