1. (a) O( N^2 )
   (b) For a quadratic algorithm, when N is increased
       by a factor of 4, the running time increases
       by a factor of 4^2 = 16. So the time will be 64 sec.
   (c) Each binary search is O( log N ), and
       there are at most N, so the total is O( N log N ).

2. (a)

public static void printReverse( BufferedReader in ) throws IOException
{
    LinkedList lines = new LinkedList( );
    String oneLine = null;

    while( ( oneLine = in.readLine( ) ) != null )
        lines.addFirst( oneLine );

    Iterator itr = lines.iterator( );
    while( itr.hasNext( ) )
        System.out.println( itr.next( ) );

    in.close( );
}

1st alternate solution uses an add at the end, with a ListIterator.
2nd alternate solution uses an ArrayList with either get, or add at
    end and reverse loop with get( ).


(b)

public static void printReverse( BufferedReader in ) throws IOException
{
    String oneLine = in.readLine( );

    if( oneLine == null )
        in.close( );
    else
    {
        printReverse( in );
        System.out.println( oneLine );
    }
}


3.

(a)

public class DoubleEnded
{
    public boolean isEmpty( )
      { return items.empty( ); }

    public void makeEmpty( )
      { items.clear( ); }

    public void insert( Object x )
    {
        Integer count = (Integer) items.get( x );

        if( count == null )
            items.put( x, new Integer( 1 ) );
        else
            items.put( x, new Integer( count.intValue( ) + 1 ) );
    }    
   
    public Object findMin( )
      { return items.firstKey( ); }

    public Object findMax( )
      { return items.lastKey( ); }

    public Object deleteMin( )
    {
        Object minVal = findMin( );
        Integer count = (Integer) items.get( minVal );

        if( count == 1 )
            items.remove( minVal );
        else
            items.put( x, new Integer( count.intValue( ) - 1 ) );

        return minVal;
    }

    ...
}

(b) All operations are O( log N ) worst case, exception isEmpty which
is O( 1 ), and makeEmpty( ) which is either O( 1 ) or O( N ),
depending on whether you charge for garbage collection.
findMin and findMax are most likely O( log N ), though it 
is conceivable that they could be O( 1 ). The reason for
all these is that a TreeMap is implemented by a binary search tree.