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) =ǉ(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.