writing a running-time recurrence

Imagine you ask a friend to count the people in a long line. Instead of counting them all yourself, you split the line in half, hand each half to a helper, wait for their two counts, and add them up plus the bit of work you did splitting. To know how long this takes, you describe the cost of the whole job in terms of the cost of the smaller jobs. That self-referential description is a recurrence.

Concretely, a running-time recurrence is an equation that expresses T(n), the time on an input of size n, using T of smaller sizes. You read it straight off the algorithm: count how many recursive calls there are and on what sizes, then add the non-recursive work done in this call. Merge sort, for example, makes two recursive calls each on half the array and then merges in linear time, so T(n) = 2 T(n/2) + O(n). Binary search recurses on one half and does O(1) extra work, giving T(n) = T(n/2) + O(1). Always pair the recurrence with a base case, such as T(1) = O(1), or it describes nothing at the bottom.

Writing the recurrence is the first and most error-prone step of analysing any recursive algorithm: once it is correct you can solve it by the recursion tree, by substitution, or by the Master Theorem. The common mistakes are miscounting the calls (Karatsuba makes three half-size multiplications, not four), forgetting the combine cost, or mislabelling the subproblem size (is it n/2 or n-1?). Honest analysis treats floors and ceilings, like T(ceil(n/2)) and T(floor(n/2)), carefully, though for asymptotics they almost never change the answer.