Java Reference
In-Depth Information
FIGURE 4-11
The time efficiencies of the ADT bag operations for two imple-
mentations, expressed in Big Oh notation
Operation
Fixed-Size Array
Linked
add(newEntry)
O(1)
O(1)
remove()
O(1)
O(1)
remove(anEntry)
O(1), O(
n
), O(
n
) O(1), O(
n
), O(
n
)
clear()
O(
n
)
O(
n
)
getFrequencyOf(anEntry)
O(
n
)
O(
n
)
contains(anEntry)
O(1), O(
n
), O(
n
) O(1), O(
n
), O(
n
)
toArray()
O(
n
)
O(
n
)
getCurrentSize(), isEmpty(), isFull()
O(1)
O(1)
As you can see, all of the operations have the same Big Oh for both implementations. This phe-
nomenon is unusual, but it reflects the simplicity of the ADT bag. Subsequent ADTs will have at
least some operations whose time efficiencies differ according to their implementations.
C
HAPTER
S
UMMARY
•
An algorithm's complexity is described in terms of the time and space required to execute it.
•
An algorithm's time requirement
f
(
n
) is of order at most
g
(
n
)—that is,
f
(
n
) is O(
g
(
n
))—if positive constants
c
and
N
exist such that
f
(
n
)
≤
c
x
g
(
n
) for all
n
≥
N
.
•
The relationships among typical growth-rate functions are as follows:
1
<
log(log
n
)
<
log
n
<
log
2
n
<
n
<
n
log
n
<
n
2
<
n
3
<
2
n
<
n
!
•
The time complexity of an ADT bag operation is the same for the fixed-size array implementation and the
linked implementation. This situation is atypical of ADTs but reflects the details of the implementations that
are possible due to the nature of a bag.
E
XERCISES
1.
Using Big Oh notation, indicate the time requirement of each of the following tasks in the worst case.
Describe any assumptions that you make.
a.
After arriving at a party, you shake hands with each person there.
b.
Each person in a room shakes hands with everyone else in the room.
c.
You climb a flight of stairs.
d.
You slide down the banister.
e.
After entering an elevator, you press a button to choose a floor.
f.
You ride the elevator from the ground floor up to the
n
th
floor.
g.
You read a book twice.
Describe a way to climb from the bottom of a flight of stairs to the top in time that is no better than O(
n
2
).
2.
