Java Reference
In-Depth Information
Question 8
The following algorithm discovers whether an array contains duplicate entries
within its first
n
elements. What is the Big Oh of this algorithm in the worst case?
Algorithm
hasDuplicates(array, n)
for
index = 0
to
n - 2
for
rest = index + 1
to
n - 1
if
(array[index]
equals
array[rest])
return true
return false
We now consider the time efficiency of two of the implementations of the ADT bag that we dis-
cussed in previous chapters.
VideoNote
Comparing ADT bag
implementations
One of the implementations of the ADT bag given in Chapter 2 used a fixed-size array to repre-
sent the bag's entries. We can now assess the efficiency of the bag operations when implemented
in this way.
4.23
Adding an entry to a bag.
Let's begin with the operation that adds a new entry to a bag.
Segment 2.10 in Chapter 2 provided the following implementation for this operation:
public boolean
add(T newEntry)
{
boolean
result =
true
;
if
(isFull())
{
result =
false
;
}
else
{
// assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
}
// end if
return
result;
}
// end add
Each step in this method—detecting whether the bag is full, assigning a new entry to an array ele-
ment, and incrementing the length—is an O(1) operation. It follows then that this method is O(1).
Intuitively, since the method adds the new entry right after the last entry in the array, we know the
index of the array element that will contain the new entry. Thus, we can make this assignment inde-
pendently of any other entries in the bag.
4.24
Searching a bag for a given entry.
The ADT bag has a method
contains
that detects whether a
bag contains a given entry. The array-based implementation of the method, as given in
Segment 2.29 of Chapter 2, is:
public
boolean
contains(T anEntry)
{
return
getIndexOf(anEntry) > -1;
}
// end contains