Java Reference
In-Depth Information
2. Move disk
n
from A to B.
3. Move
n
-
1 disks from C to B with the assistance of tower A.
The complexity of this algorithm is measured by the number of moves. Let
T
(
n
) denote the
number of moves for the algorithm to move
n
disks from tower A to tower B with
T
(1)
=
1.
Thus,
T
(
n
)
=
T
(
n
-
1)
+
1
+
T
(
n
-
1)
=
2
T
(
n
-
1)
+
1
=
2(2
T
(
n
-
2)
+
1)
+
1
=
2(2(2
T
(
n
-
3)
+
1)
+
1)
+
1
2
n
-
1
T
(1)
2
n
-
2
=
+
+ c +
+
2
1
2
n
-
1
2
n
-
2
(2
n
O
(2
n
)
=
+
+ c +
+
=
-
=
2
1
1)
An algorithm with
O
(2
n
) time complexity is called an
exponential algorithm
, and it exhibits
an exponential growth rate. As the input size increases, the time for the exponential algorithm
grows exponentially. Exponential algorithms are not practical for large input size. Suppose
the disk is moved at a rate of 1 per second. It would take 2
32
/(365 * 24 * 60 * 60)
O
(2
n
)
exponential time
=
136 years
to move 32 disks and 2
64
/(365 * 24 * 60 * 60)
=
585 billion years to move 64 disks.
22.4.4 Common Recurrence Relations
Recurrence relations
are a useful tool for analyzing algorithm complexity. As shown in
the preceding examples, the complexity for binary search, selection sort, and the Tower
n
2
of Hanoi is
T
(
n
)
=
T
¢
≤
+
O
(1),
T
(
n
)
=
T
(
n
-
1)
+
O
(
n
), and
T
(
n
)
=
2
T
(
n
-
1)
+
O
(1),
respectively. Table 22.2 summarizes the common recurrence relations.
T
ABLE
22.2
Common Recurrence Functions
Recurrence Relation
Result
Example
T
(
n
)
=
T
(
n
/2)
+
O
(1)
T
(
n
)
=
O
(log
n
)
Binary search, Euclid's GCD
T
(
n
)
=
T
(
n
-
1)
+
O
(1)
T
(
n
)
=
O
(
n
)
Linear search
T
(
n
)
=
2
T
(
n
/2)
+
O
(1)
T
(
n
)
=
O
(
n
)
Checkpoint Question 22.20
T
(
n
)
=
2
T
(
n
/2)
+
O
(
n
)
T
(
n
)
=
O
(
n
log
n
)
Merge sort (Chapter 23)
O
(
n
2
)
T
(
n
)
=
T
(
n
-
1)
+
O
(
n
)
T
(
n
)
=
Selection sort
O
(2
n
)
T
(
n
)
=
2
T
(
n
-
1)
+
O
(1)
T
(
n
)
=
Tower of Hanoi
T
(
n
)
=
O
(2
n
)
T
(
n
)
=
T
(
n
-
1)
+
T
(
n
-
2)
+
O
(1)
Recursive Fibonacci algorithm
22.4.5 Comparing Common Growth Functions
The preceding sections analyzed the complexity of several algorithms. Table 22.3 lists some
common growth functions and shows how growth rates change as the input size doubles from
n
=
25 to
n
=
50.
Search WWH ::
Custom Search