Runtime

complexity-theory

Definition

Runtime

Runtime is the number of steps required to execute a program or algorithm and is describe by a function $T(n)$ for an input size $n$.

Types

Wort-case Runtime

Definition

Worst-Case Complexity

Worst-case complexity is the greatest possible runtime of a program for a given input size $n$.

Link to original

Average-case Runtime

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.

Link to original

Best-case Runtime

Definition

Best-case Runtime

Best-case runtime is the smallest possible runtime of a program for a given input size $n$.

Link to original

Examples

Simple Example

Given the following simple Sum program:

Sum(A, x):
    sum <- 0
    for i <- 0 to n-1:
        if A[i] > x:
            sum <- sum + A[i]
    print(sum)

The algorithm consists of multiple statements with different constant costs:

Statement	Constant Cost	Execution Count
sum <- 0	$c_1$	$1$
for i <- 0 to n	$c_2$	$n$
if A[i] > x	$c_3$	$n$
sum <- sum + A[i]	$c_4$	$j$ with $0\le j\le n$
print(sum)	$c_5$	$1$

The total cost of the algorithm is the sum of the constant costs weighted by the execution counts:

$$\begin{array}{rl}T(n)& =c_1\cdot 1+c_2\cdot n+c_3\cdot n+c_4\cdot j+c_5\cdot 1\\ & =(c_2+c_3)\cdot n+c_4\cdot j+(c_1+c_5)\end{array}$$

The best-case runtime with $j=0$ is:

$$\begin{array}{rl}T(n)& =\underset{\text{constant}}{\underbrace{(c_2+c_3)}}\cdot n+\underset{\text{constant}}{\underbrace{(c_1+c_5)}}\\ & =a_1\cdot n+b_1\end{array}$$

The worst-case runtime with $j=n$ is:

$$\begin{array}{rl}T(n)& =\underset{\text{constant}}{\underbrace{(c_2+c_3+c_4)}}\cdot n+\underset{\text{constant}}{\underbrace{(c_1+c_5)}}\\ & =a_2\cdot n+b_2\end{array}$$