Time complexity - Mathematical Concepts
Express abstract time as a function of the size of the input.
Suppose
A
is an algorithm and
Input
represents an input to
A.
Let |
Input
| =
n
be the size of
Input.
The number of steps consumed in executing
A
over
Input
is
Time
_{A}
(
Input
)
The
best case
time complexity is
Min
_{|Input| = n}
Time
_{A}
(
Input
)
The
worst
case time complexity is
T
_{A}
(
n
) = Max
_{|Input| = n}
Time
_{A}
(
Input
).
The
average case
time complexity is
average
_{|Input| = n}
Time
_{A}
(
Input
).
CS1104 Main Page
Last Updated 01/05/2000
©
L.Heath
, 2000