problem instance

An instance is one specific question, where the problem is the whole family of questions. If the problem is "multiply two numbers," then "multiply 23 by 47" is one instance of it. The problem is the template with blanks; an instance is the template with the blanks filled in by concrete data. You feed an instance to an algorithm and get back an answer for that instance.

Precisely, a problem fixes the set of all legal inputs, and each particular legal input is an instance. For the Sorting problem, the list [3,1,2] is an instance, the list [9,9,9] is another instance, and the empty list is yet another. Each instance has its own correct answer (for [3,1,2] it is [1,2,3]), but they are all governed by the same single specification of what "sorted" means. An algorithm solves the problem only if it returns the correct answer on every instance, including odd or extreme ones like the empty list or a list that is already sorted.

This distinction shows up everywhere in analysis. When we talk about how long an algorithm takes, we mean how long it takes on instances of a given size — and crucially, different instances of the same size can take different times (this is exactly what worst-, best-, and average-case capture). When someone says "this algorithm is O(n log n)," they are making a claim about the whole family of instances, not about one lucky example.