Practice for Test 1

1. Find the big-O complexity of each piece of code below in terms of N.

   1. for (int i = 0; i < N; i ++)
        print(i);
      

   2. for (int i = 0; i < N/2; i ++)
        print(i);
      

   3. for (int i = 0; i < N; i ++)
        for (int j = 0; j < N/2; j++)
           print(i);
      

   4. for (int i = 0; i < N; i ++)
        for (int j = 0; j < i; j++)
           print(i);
      

   5. for (int i = 0; i < N; i ++)
        for (int j = 0; j < 5; j++)
           print(i);
      

   6. for (int i = 1; i < N/2; i*=2)
        print(i);
      

   7. for (int i = N; i > 1; i/=2)
        print(i);
      

   8. for (int i = N; i > N-5; i--)
        print(i);
      

2. Write Java code that prints the "border" (first and last rows, first and last columns) of a two-dimensional array a. No fancy formatting in output -- just print first row, last row, first col, last col.

   If a is N x N (square), what is the complexity of this code?

3. Write code that counts the number of occurrences of integer x in array a.

   Do the same for a two-dimensional array a.

4. Write code that reads in N integers in the range -25..+25 and counts the number of occurrences of each integer. N could be arbitrarily large.

5. Write code that creates an array of 10 Square objects, fills it with new Square objects (use the default constructor for Square), and prints each Square. Assume that class Square has a printSquare method.