Java Reference
In-Depth Information
The linear search algorithm requires
n
comparisons in the worst case and
n
/2 comparisons
in the average case if you are nearly always looking for something known to be in the list.
Using the Big
O
notation, both cases require
O
(
n
) time. The multiplicative constant (1/2) can
be omitted. Algorithm analysis is focused on growth rate. The multiplicative constants have
no impact on growth rates. The growth rate for
n
/2 or 100
n
is the same as for
n
, as illustrated
in Table 22.1. Therefore,
O
(
n
)
ignore multiplicative constants
=
O
(
n
/2)
=
O
(100
n
).
T
ABLE
22.1
Growth Rates
f
(
n
)
n
n
/2
100
n
n
100
100
50
10000
200
200
100
20000
2
2
2
f
(200)
f
(100)
Consider the algorithm for finding the maximum number in an array of
n
elements. To find
the maximum number if
n
is 2, it takes one comparison; if
n
is 3, two comparisons. In general,
it takes
n
1 comparisons to find the maximum number in a list of
n
elements. Algorithm
analysis is for large input size. If the input size is small, there is no significance in estimating
an algorithm's efficiency. As
n
grows larger, the
n
part in the expression
n
-
large input size
1 dominates the
complexity. The Big
O
notation allows you to ignore the nondominating part (e.g.,
-
-
1 in the
ignore nondominating terms
expression
n
-
1) and highlight the important part (e.g.,
n
in the expression
n
-
1). There-
fore, the complexity of this algorithm is
O
(
n
).
The Big
O
notation estimates the execution time of an algorithm in relation to the input
size. If the time is not related to the input size, the algorithm is said to take
constant time
with
the notation
O
(1). For example, a method that retrieves an element at a given index in an array
takes constant time, because the time does not grow as the size of the array increases.
The following mathematical summations are often useful in algorithm analysis:
constant time
useful summations
n
(
n
-
1)
O
(
n
2
)
1
+
2
+
3
+ c +
(
n
-
2)
+
(
n
-
1)
=
=
2
n
(
n
+
1)
O
(
n
2
)
1
+
2
+
3
+ c +
(
n
-
1)
+
n
=
=
2
a
n
+
1
-
1
a
0
a
1
a
2
a
3
a
(
n
-
1)
a
n
O
(
a
n
)
+
+
+
+ c +
+
=
1
=
a
-
2
n
+
1
-
1
2
0
2
1
2
2
2
3
2
(
n
-
1)
2
n
2
n
+
1
O
(2
n
)
+
+
+
+ c +
+
=
1
=
-
1
=
2
-
Note
Time complexity
is a measure of execution time using the Big-O notation. Similarly, you
can also measure
space complexity
using the Big-O notation.
Space complexity
meas-
ures the amount of memory space used by an algorithm. The space complexity for most
algorithms presented in the topic is
O
(
n
). i.e., they exibit linear growth rate to the input
size. For example, the space complexity for linear search is
O
(
n
).
time complexity
space complexity
22.1
✓
✓
Why is a constant factor ignored in the Big
O
notation? Why is a nondominating term
ignored in the Big
O
notation?
Check
Point
22.2
What is the order of each of the following functions?
(
n
2
1)
2
,
(
n
2
log
2
n
)
2
n
+
+
,
n
3
100
n
2
n
,2
n
100
n
2
45
n
,
n
2
n
n
2
2
n
+
+
+
+
+
n
Search WWH ::
Custom Search