The Efficiency of Algorithms - Data Structures and Abstractions with Java - page 99

By calling the private method getIndexOf , the method locates the first array element, if any, that
contains the entry we seek. Let's examine getIndexOf , as described in Segment 2.28 of Chapter 2:
private int getIndexOf(T anEntry)
{

int where = -1;
boolean found = false ;
for ( int index = 0; !found && (index < numberOfEntries); index++)
{

if (anEntry.equals(bag[index]))
{

found = true ;
where = index;
} // end if
} // end for
return where;
} // end getIndexOf

This method searches the array bag for the given entry anEntry . The basic operation for the method is
comparison. As we described earlier in Segment 4.10, the method would make one comparison in the
best case and n comparisons in the worst case, assuming that the bag contains n entries. Typically, the
method would make about n / 2 comparisons. We can conclude that the method contains is O(1) in
the best case and O( n ) in both the worst and average cases.

Note: To simplify our example, we have considered a fixed-size array. Typically, an array-
based bag resizes the array as needed. Doubling the size of an array is an O( n ) operation. As
Segment 2.35 of Chapter 2 noted, the next n additions would share the cost of this doubling.

Question 9 What is the Big Oh of the bag's remove methods? Assume that a fixed-size
array represents the bag, and use an argument similar to the one we just made for contains .

Question 10 Repeat Question 9, but instead analyze the method getFrequencyOf .
Question 11 Repeat Question 9, but instead analyze the method toArray .

A Linked Implementation
4.25

Adding an entry to a bag. Now consider a linked implementation of the ADT bag as given in
Chapter 3. Let's begin with Segment 3.12 and the method add that adds an entry to a bag:

public boolean add(T newEntry) // OutOfMemoryError possible
{

// add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // make new node reference rest of chain

// (firstNode is null if chain is empty)

firstNode = newNode; // new node is at beginning of chain

numberOfEntries++;
return true ;
} // end add
All of the statements in this method represent O(1) operations, and so the method is O(1).