Java Reference
In-Depth Information
Insertion sort has one desirable property: Its performance is O(n) if the array is
already sortedȌsee Exercise R14.13. This is a useful property in practical
applications, in which data sets are often partially sorted.
A
DVANCED
T
OPIC
14.2: Oh, Omega, and Theta
We have used the big-Oh notation somewhat casually in this chapter, to describe
the growth behavior of a function. Strictly speaking, f(n)=O(g(n)) means that f
grows no faster than g. But it is permissible for f to grow much slower. Thus, it is
technically correct to state that f(n)=n
2
+5nɨ3 is O(n
3
) or even O(n
10
).
Computer scientists have invented additional notation to describe the growth
behavior of functions more accurately. The expression
f(n) =lj(g(n))
638
639
means that f grows at least as fast as g, or, formally, that for all n larger than some
threshold, the ratio f(n)/g(n) ʏ C for some constant value C. (The Ɗ symbol is the
capital Greek letter omega.) For example, f(n)=n
2
+5nɨ3 is Ɗ(n
2
) or even Ɗ(n).
The expression
f(n) =ƹ(g(n))
means that f and g grow at the same rateȌthat is, both f(n)=O(g(n)) and
f(n)=Ɗ(g(n)) hold. (The ź symbol is the capital Greek letter theta.)
The ź notation gives the most precise description of growth behavior. For
example, f(n)=n
2
+5nɨ3 is ź(n
2
) but not ź(n) or ź(n
3
).
The Ɗ and ź notation is very important for the precise analysis of algorithms.
However, in casual conversation it is common to stick with big-Oh, while still
giving as good an estimate as one can.
14.4 Merge Sort
In this section, you will learn about the merge sort algorithm, a much more efficient
algorithm than selection sort. The basic idea behind merge sort is very simple.
