complexity-theory Definition Average-case Runtime Average-case runtime is the average runtime of a program for a given input size n. Determining the average-case runtime might be troublesome since it depends on the distribution of the input size.