Java Reference
In-Depth Information
Array
result in four more recursive
sortArray
calls, each with a subarray approximately a
quarter of the original array's size, along with two calls to
merge
that each require, at worst,
n
/2 - 1 comparisons, for a total number of comparisons of
O
(
n
). This process continues,
each
sortArray
call generating two additional
sortArray
calls and a
merge
call, until the al-
gorithm has
split
the array into one-element subarrays. At each level,
O
(
n
) comparisons are
required to
merge
the subarrays. Each level splits the the arrays in half, so doubling the array
size requires one more level. Quadrupling the array size requires two more levels. This pat-
tern is logarithmic and results in log
2
n
levels. This results in a total efficiency of
O
(
n
log
n
)
.
Sorting Algorithms
Figure 19.7 summarizes the searching and sorting algorithms covered in this chapter with
the Big O for each. Figure 19.8 lists the Big O values we've covered in this chapter along
with a number of values for
n
to highlight the differences in the growth rates.
Algorithm
Location
Big O
Searching Algorithms:
Linear search
Section 19.2
O
(
n
)
Binary search
Section 19.4
O
(log
n
)
Recursive linear search
Exercise 19.8
O
(
n
)
Recursive binary search
Exercise 19.9
O
(log
n
)
Sorting Algorithms:
Selection sort
O
(
n
2
)
Section 19.6
O
(
n
2
)
Insertion sort
Section 19.7
Merge sort
Section 19.8
O
(
n
log
n
)
O
(
n
2
)
Bubble sort
Exercises 19.5 and 19.6
Fig. 19.7
|
Searching and sorting algorithms with Big O values.
n
=
O
(log
n
)
O
(
n
)
O
(
n
log
n
)
O
(
n
2
)
1
0
1
0
1
2
1
2
2
4
3
1
3
3
9
4
1
4
4
16
5
1
5
5
25
10
1
10
10
100
100
2
100
200
10,000
10
6
1000
3
1000
3000
10
12
1,000,000
6
1,000,000
6,000,000
10
18
1,000,000,000
9
1,000,000,000
9,000,000,000
Fig. 19.8
|
Number of comparisons for common Big O notations.
