the input size

When we say an algorithm runs in time O(n^2), the n is doing a lot of quiet work, and it pays to ask: n what? The input size is the number we measure the cost against. Think of it as the size of the box the problem arrives in: a longer string, a bigger list, a graph with more roads. The honest convention is to count the number of symbols it takes to write the input down on the machine's tape, so n is the length of the encoded input, not some informal notion of how complicated the problem feels.

Choosing the right n is part of stating the problem. For a sorting task n is usually the number of items in the list. For a graph problem we often use n for the number of vertices and m for the number of edges, and report time like O(n + m). For a single number like 'is N prime?' the subtlety bites: N itself can be astronomically large, but you write it in only about log N binary digits, so the input size is roughly log N, not N. An algorithm that takes N steps on an input of size n = log N is actually exponential in n, because N = 2^n. Getting this right is why a careful course always says 'time as a function of the size of the input'.

This is exactly why the next idea, a reasonable encoding, matters: how you write the input down decides what n is, and a sneaky encoding can make a slow algorithm look fast or a fast one look slow. Fix a sensible way to write inputs first; then the question 'how does the running time grow with n?' has a clean, model-independent answer.