complexity-theory Definition Best-case Runtime Best-case runtime is the smallest possible runtime of a program for a given input size n.