Java Reference
In-Depth Information
T
ABLE
22.3
Change of Growth Rates
Function
Name
=
f
(50)/
f
(25)
n
50
n
=
25
O
(1)
Constant time
1
1
1
O
(log
n
)
Logarithmic time
4.64
5.64
1.21
O
(
n
)
Linear time
25
50
2
O
(
n
log
n
)
Log-linear time
116
282
2.43
O
(
n
2
)
Quadratic time
625
2,500
4
O
(
n
3
)
Cubic time
15,625
125,000
8
O
(2
n
)
10
7
Exponential time
3.36
*
10
7
1.27
*
10
15
3.35
*
These functions are ordered as follows, as illustrated in Figure 22.1.
O
(
n
2
)
O
(
n
3
)
O
(2
n
)
O
(1)
6
O
(log
n
)
6
O
(
n
)
6
O
(
n
log
n
)
6
6
6
f(n)
O
(2
n
)
O
(
n
3
)
O
(
n
2
)
O
(
n
log
n
)
O
(
n
)
O
(log
n
)
O
(1)
n
F
IGURE
22.1
As the size
n
increases, the function grows.
22.8
Put the following growth functions in order:
5
n
3
4032
,44log
n
,10
n
log
n
, 500, 2
n
2
,
✓
✓
Check
Point
2
n
45
,3
n
22.9
Estimate the time complexity for adding two
n
*
m
matrices, and for multiplying an
n
*
m
matrix by an
m
*
k
matrix.
22.10
Describe an algorithm for finding the occurrence of the max element in an array.
Analyze the complexity of the algorithm.
22.11
Describe an algorithm for removing duplicates from an array. Analyze the complex-
ity of the algorithm.
22.12
Analyze the following sorting algorithm:
for
(
int
i =
0
; i < list.length
- 1
; i++) {
if
(list[i] > list[i +
1
]) {
swap list[i] with list[i +
1
];
i =
-1
;
}
}
22.13
Analyze the complexity for computing a polynomial
f (x)
of degree
n
for a given
x
value using a brute-force approach and the Horner's approach, respectively. A brute-
force approach is to compute each term in the polynomial and add them together. The
Horner's approach was introduced in Section 6.7.
f
(
x
)
a
n
x
n
a
n
-
1
x
n
-
1
a
n
-
2
x
n
-
2
a
1
x
1
=
+
+
+ c +
+
a
0
Search WWH ::
Custom Search