Lab 3.
Iterator and Complexity
CS203,
Spring 2006
1. (20pt) Complete the ArrayList
class which inherits from AbstractList
and
implements the List
interface. Test your ArrayList with
ListTest.java and
verify the output.
For the following exercises, put your answers in a text file lab3.txt or an MS
Word file lab3.doc.
2. (10pt) Show 1000+2000N+N2=O(N2)
using the steps outlined in the lectures
notes.
3. (20pt) Give the time complexity of the following algorithm/code in
the Big-O notation:
(a). binary search: best case and worst case
(b).
long factorial( int n )
{
return n <= 1 ? 1 : factorial(n-1) * n;
}
(c).
sum = 0;
for( i=0 ; i < n ; ++i )
for( j=0 ; j < n ; ++j )
++sum;
(d).
sum = 0;
for( i=0 ; i < n ; ++i )
for( j=0 ; j < n*n; ++j )
++sum;
(e).
sum = 0;
for( i=0 ; i < n ; ++i )
for( j=0 ; j < i ; ++j )
++sum;
4. Turn in all the source code files and lab3.txt (or lab3.doc) through
CSNS