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
The Efficiency of Implementations of the ADT Bag
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
An Array-Based Implementation
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
 
 
 
Search WWH ::




Custom Search