Java Reference
In-Depth Information
In simple terms,
f
(
n
) is O(
g
(
n
)) means that
c
x
g
(
n
) provides an
upper bound
on
f
(
n
)'s growth
rate when
n
is large enough. For all data sets of a sufficient size, the algorithm will always require
fewer than
c
x
g
(
n
) basic operations.
Figure 4-5 illustrates the formal definition of Big Oh. You can see that when
n
is large
enough—that is, when
n
N
—
f
(
n
) does not exceed
c
x
g
(
n
). The opposite is true for smaller values
of
n
. That is unimportant, since we can ignore these values of
n
.
≥
FIGURE 4-5
An illustration of the definition of Big Oh
25
c g(n)
20
f(n)
15
10
5
0
N
15
n
20
25
30
0
5
10
4.14
Example.
In Segment 4.6, we said that if an algorithm uses 5
n
+
3 operations, it requires time pro-
portional to
n
. We now can show that 5
n
+
3 is O(
n
) by using the formal definition of Big Oh.
When
n
≥
3, 5
n
+
3
≤
5
n
+
n
=
6
n
. Thus, if we let
f
(
n
)
=
5
n
+
3,
g
(
n
)
=
n
,
c
=
6, and
N
=
3, we
have shown that
f
(
n
)
3, or 5
n
+
3
=
O(
n
). That is, if an algorithm requires time
directly proportional to 5
n
+
3, it is O(
n
).
Other values for the constants
c
and
N
will also work. For example, 5
n
+
3
≤
6
g
(
n
) for
n
≥
≤
5
n
+
3
n
=
8
n
when
n
≥
1. Thus, by choosing
c
= 8 and
N
=
1, we have shown that 5
n
+
3 is O(
n
).
You need to be careful when choosing
g
(
n
). For example, we just found that 5
n
+
3
≤
8
n
when
9. So why wouldn't we let
g
(
n
)
=
n
2
and conclude that our algorithm is
O(
n
2
)? Although this conclusion is correct, it is not as good—or
tight
—as it could be. You want the
upper bound on
f
(
n
) to be as small as possible.
1. But 8
n
<
n
2
when
n
n
≥
≥
Note:
The upper bound on an algorithm's time requirement should be as small as possible
and should involve simple functions like the ones given in Figure 4-4.
Example.
Let's show that 4
n
2
+
50
n
-
10 is O(
n
2
). It is easy to see that
4.15
4
n
2
+
50
n
-
10
4
n
2
+
50
n
for any
n
≤
50
n
2
for
n
Since 50
n
≤
≥
50,
4
n
2
+
50
n
-
10
4
n
2
+
50
n
2
=
54
n
2
for
n
≤
≥
50
Thus, with
c
=
54 and
N
=
50, we have shown that 4
n
2
+
50
n
-
10 is O(
n
2
).
