Java Reference
In-Depth Information
Display 15.31
Some Values of a Running Time Function
Input Size
Running Time
10 numbers
2 seconds
100 numbers
2.1 seconds
1,000 numbers
10 seconds
10,000 numbers
2.5 minutes
function
The table is a description of what is called a
function
in mathematics. Just as a
(non-
void
) Java method takes an argument and returns a value, so too does this func-
tion take an argument, which is an input size, and returns a number, which is the time
the program takes on an input of that size. If we call this function
T
, then
T
(10) is 2
seconds,
T
(100) is 2.1 seconds,
T
(1,000) is 10 seconds, and
T
(10,000) is 2.5 min-
utes. The table is just a sample of some of the values of this function
T
. The program
will take some amount of time on inputs of every size. So although they are not shown
in the table, there are also values for
T
(1),
T
(2), . . . ,
T
(101),
T
(102), and so forth.
For any positive integer
N
,
T
(
N
) is the amount of time it takes for the program to
sort
N
numbers. The function
T
is called the
running time
of the program.
So far we have been assuming that this sorting program will take the same amount
of time on any list of
N
numbers. That need not be true. Perhaps it takes much less
time if the list is already sorted or almost sorted. In that case,
T
(
N
) is defined to be
the time taken by the “hardest” list, that is, the time taken on that list of
N
numbers
that makes the program run the longest. This is called the
worst-case running time
.
In this chapter we will always mean worst-case running time when we give a running
time for an algorithm or for some code.
The time taken by a program or algorithm is often given by a formula, such as 4
N
running time
worst-case
running time
3, 5
N
+
4, or
N
2
. If the running time
T
(
N
) is 5
N
+
5, then on inputs of size
N
the
program will run for 5
N
+
5 time units.
Below is some code to search an array
a
with
N
elements to determine whether a
particular value
target
is in the array:
+
int
i = 0;
boolean
found =
false
;
while
(( i < N) && !(found))
{
if
(a[i] == target)
found =
true
;
else
i++;
}
