P - a program with input I that runs in time t(I)

D - the set of all valid inputs for P(I)

size(I) - size of input I

size :D ->  ℕ

(Subscript[D, n]) - the set of all valid inputs of size n 

		(Subscript[D, n]) = {I ∈ D | size(I) = n}


Running time as a function of size of input

		Time : ℕ -> (SuperPlus[ℝ])



Worst-case running time

		T(n) = max{t(I) |I ∈ (Subscript[D, n])}



Average-case running time

	Given probability distribution (Subscript[p, n]) on (Subscript[D, n]),

		(Subscript[T, avg])(n) = ∑{t(I)×(Subscript[p, n])(I) |I ∈ (Subscript[D, n])}


In the case of uniform distribution of probability:

(Subscript[T, avg])(n) = ((∑{t(I) |I ∈ (Subscript[D, n])})/(|(Subscript[D, n])|))

Example.

QuickSort:

D - the set of all permutations of some initial interval of the set of natural numbers ℕ 

size(I) = number of elements in I (to be sorted)

(Subscript[D, n]) - the set of all permutations of {0, ..., n - 1}

		|(Subscript[D, n])| = n!

Worst-case running time:

		T(n) ~ (n^2) 

The worst input of size n is the sequence 
<0, ..., n - 1>. 


Average-case running time:

Assume that all inputs of size n to QuickSort are equally likely (with probability (1/(n!))).

		(Subscript[T, avg])(n) ~ n (Subscript[log, 2])n

Plot[Tooltip[{x Log[x],(x^2)}],{x,0,10}]