Java Reference
In-Depth Information
1
2
The factor cancels out in comparisons of this kind. We will simply say, ȒThe
number of visits is of order n
2
ȓ. That way, we can easily see that the number of
comparisons increases fourfold when the size of the array doubles: (2n)
2
=4n
2
.
To indicate that the number of visits is of order n
2
, computer scientists often use
big-Oh notation: The number of visits is O(n
2
). This is a convenient shorthand.
In general, the expression f(n)=O(g(n)) means that f grows no faster than g, or, more
formally, that for all n larger than some thresh-old, the ratio f(n)/g(n) ʎ C for some
constant value C. The function g is usually chosen to be very simple, such as n
2
in our
example.
Computer scientists use the big-Oh notation f(n)=O(g(n)) to express that the
function f grows no faster than the function g.
To turn an exact expression such as
1
n
2
5
2
+
n ɨ3
2
into big-Oh notation, simply locate the fastest-growing term, n
2
, and ignore its
constant coefficient, no matter how large or small it may be.
