Java Reference
In-Depth Information
This section analyzes the complexity of several well-known algorithms: binary search,
selection sort, and Tower of Hanoi.
Key
Point
22.4.1 Analyzing Binary Search
The binary search algorithm presented in Listing 7.7, BinarySearch.java, searches for a key in
a sorted array. Each iteration in the algorithm contains a fixed number of operations, denoted
by
c
. Let
T
(
n
) denote the time complexity for a binary search on a list of
n
elements. Without
loss of generality, assume
n
is a power of 2 and
k
binary search animation on
the Companion Website
=
log
n
. Since a binary search eliminates
half of the input after two comparisons,
n
2
n
2
2
n
2
k
T
(
n
)
=
T
¢
≤
+
c
=
T
¢
≤
+
c
+
c
=
T
¢
≤
+
kc
=
T
(1)
+
c
log
n
=
1
+
(log
n
)
c
=
O
(log
n
)
Ignoring constants and nondominating terms, the complexity of the binary search algorithm
is
O(
log
n
). An algorithm with the
O(
log
n
) time complexity is called a
logarithmic algorithm
and it exhibits a logarithmic growth rate. The base of the log is 2, but the base does not affect
a logarithmic growth rate, so it can be omitted. The logarithmic algorithm grows slowly as the
problem size increases. In the case of binary search, each time you double the array size, at most
one more comparison will be required. If you square the input size of any logarithmic time algo-
rithm, you only double the time of execution. So a logarithmic-time algorithm is very efficient.
logarithmic time
22.4.2 Analyzing Selection Sort
The selection sort algorithm presented in Listing 7.8, SelectionSort.java, finds the smallest
element in the list and swaps it with the first element. It then finds the smallest element
remaining and swaps it with the first element in the remaning list, and so on until the remain-
ing list contains only one element left to be sorted. The number of comparisons is
n
selection sort animation on
the Companion Website
-
1 for
the first iteration,
n
2 for the second iteration, and so on. Let
T
(
n
) denote the complexity
for selection sort and
c
denote the total number of other operations such as assignments and
additional comparisons in each iteration. Thus,
-
T
(
n
)
=
(
n
-
1)
+
c
+
(
n
-
2)
+
c
+ c +
2
+
c
+
1
+
c
n
2
2
(
n
-
1)(
n
-
1
+
1)
n
2
+
=
+
c
(
n
-
1)
=
-
cn
-
c
2
O
(
n
2
)
=
Therefore, the complexity of the selection sort algorithm is
O
(
n
2
).
22.4.3 Analyzing the Tower of Hanoi Problem
The Tower of Hanoi problem presented in Listing18.8, TowerOfHanoi.java, recursively
moves
n
disks from tower A to tower B with the assistance of tower C as follows:
1. Move the first
n
-
1 disks from A to C with the assistance of tower B.
Search WWH ::
Custom Search