Java Reference
In-Depth Information
1
n
2
5
2
+
n ɨ3
2
635
636
We obtain a quadratic equation in n. That explains why the graph of
Figure 1
looks
approximately like a parabola.
Now let us simplify the analysis further. When you plug in a large value for n (for
1
2
n
2
5
2
example, 1,000 or 2,000), then is 500,000 or 2,000,000. The lower term, n ɨ3,
doesn't contribute much at all; it is only 2,497 or 4,997, a drop in the bucket
compared to the hundreds of thousands or even millions of comparisons specified by
1
2
n
2
the term. We will just ignore these lower-level terms. Next, we will ignore the
1
2
constant factor . We are not interested in the actual count of visits for a single n. We
want to compare the ratios of counts for different values of n. For example, we can
say that sorting an array of 2,000 numbers requires four times as many visits as
sorting an array of 1,000 numbers:
(
1
2
2000
2
)
=4
(
1
2
1000
2
)
