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


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
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: