Java Reference
In-Depth Information
Note:
To show that
f
(
n
) is O(
g
(
n
)), replace the smaller terms in
f
(
n
) with larger terms until
only one term is left.
Question 3
Show that 3
n
2
+ 2
n
is O(2
n
). What values of
c
and
N
did you use?
4.16
Example: Show that log
b
n
is O(log
2
n
).
Let
L
=
log
b
n
and
B
=
log
2
b
. From the meaning of a log-
arithm, we can conclude that
n
=
b
L
and
b
=
2
B
. Combining these two conclusions, we have
n
=
b
L
=
(2
B
)
L
=
2
BL
Thus, log
2
n
=
BL
=
B
log
b
n
or, equivalently, log
b
n
=
(1
/
B
)
log
2
n
for any
n
≥
1. Taking
c
=
1
/
B
and
N
=
1 in the definition of Big Oh, we reach the desired conclusion.
It follows from this example that the general behavior of a logarithmic function is the same
regardless of its base. Often the logarithms used in growth-rate functions are base 2. But since the
base really does not matter, we typically omit it.
Note:
The base of a logarithm in a growth-rate function is usually omitted, since O(log
a
n
)
is O(log
b
n
).
Note:
Identities
The following identities hold for Big Oh notation:
O(
k
g
(
n
))
=
O(
g
(
n
)) for a constant
k
O(
g
1
(
n
))
+
O(
g
2
(
n
))
=
O(
g
1
(
n
)
+
g
2
(
n
))
O(
g
1
(
n
))
x
O(
g
2
(
n
))
=
O(
g
1
(
n
)
x
g
2
(
n
))
O(
g
1
(
n
)
+
g
2
(
n
)
+
. . .
+
g
m
(
n
))
=
O(max(
g
1
(
n
),
g
2
(
n
), . . .,
g
m
(
n
))
O(max(
g
1
(
n
),
g
2
(
n
), . . .,
g
m
(
n
))
=
max(O(
g
1
(
n
)), O(
g
2
(
n
)), . . ., O(
g
m
(
n
)))
By using these identities and ignoring smaller terms in a growth-rate function, you can usu-
ally find the order of an algorithm's time requirement with little effort. For example, if the
growth-rate function is 4
n
2
+
50
n
-
10,
O(4
n
2
+
50
n
-
10)
=
O(4
n
2
)
by ignoring the smaller terms
=
O(
n
2
)
by ignoring the constant multiplier
Question 4
If P
k
(
n
)
=
a
0
n
k
+
a
1
n
k
- 1
+
. . .
+
a
k
for
k
> 0 and
n
> 0, what is O(P
k
(
n
))?
