Java Reference
In-Depth Information
When
n
is 1,
countDown
displays 1. This is the base case and requires a constant amount of
time. When
n
>
1, the method requires a constant amount of time for both the
println
statement
and the comparison. In addition, it needs time to solve the smaller problem represented by the
recursive call. If we let
t
(
n
) represent the time requirement of
countDown(n)
, we can express these
observations by writing
t
(1)
=
1
t
(
n
)
=
1
+
t
(
n
-
1) for
n
>
1
The equation for
t
(
n
) is called a
recurrence relation
, since the definition of the function
t
con-
tains an occurrence of itself—that is, a recurrence. What we need is an expression for
t
(
n
) that is not
given in terms of itself. One way to find such an expression is to pick a value for
n
and to write out
the equations for
t
(
n
),
t
(
n
-
1), and so on, until we reach
t
(1). From these equations, we should be
able to guess at an appropriate expression to represent
t
(
n
). We then need only to prove that we are
right. This is actually easier than it sounds.
7.23
Solving a recurrence relation.
To solve the previous recurrence relation for
t
(
n
), let's begin with
n
=
4. We get the following sequence of equations:
t
(4)
=
1
+
t
(3)
t
(3)
=
1
+
t
(2)
t
(2)
=
1
+
t
(1)
=
1
+
1
=
2
Substituting 2 for
t
(2) in the equation for
t
(3) results in
t
(3)
=
1
+
2
=
3
Substituting 3 for
t
(3) in the equation for
t
(4) results in
t
(4)
=
1
+
3
=
4
It appears that
t
(
n
)
=
n
for
n
≥
1
We can start with a larger value of
n
, get the same result, and convince ourselves that it is true.
But we need to
prove
that this result is true for every
n
≥
1. This is not hard to do.
7.24
Proving that
t
(
n
)
=
n
.
To prove that
t
(
n
)
=
n
for
n
≥
1, we begin with the recurrence relation for
t
(
n
),
since we know it is true:
t
(
n
)
=
1
+
t
(
n
-
1) for
n
>
1
We need to replace
t
(
n
-
1) on the right side of the equation. Now if
t
(
n
-
1)
=
n
-
1 when
n
>
1, the
following would be true for
n
>
1:
t
(
n
)
=
1
+
n
-
1
=
n
Thus, if we can find an integer
k
that satisfies the equation
t
(
k
)
=
k
, the next larger integer will also
satisfy it. By a similar chain of reasoning, the equation is true for all integers larger than
k
. Since we
are given that
t
(1)
=
1, all integers larger than 1 will satisfy the equation. This proof is an example
of a
proof by induction
.
To conclude, we now know that
countDown
's time requirement is given by the function
t
(
n
)
=
n
.
Thus, the method is O(
n
).
