Data Structures, Algorithms, & Applications in Java
Chapter 5, Exercise 21

(a)

We scan the list from left to right skipping over elements that are not to be saved. Elements to be saved are moved to their new positions as they are encountered. The method dataStructures.ArrayLinearListWithHalf.half is given below.

/** Save element[i], for i = 0, 2, 4, ...
  * Compact saved elements. */
public void half()
{
   for (int i = 2; i < size; i += 2)
      element[i/2] = element[i];

   int newSize = (size + 1) / 2;
   for (int i = newSize; i < size; i++)
      element[i] = null;   // enable garbage collection

   size = newSize;
}

(b)

Each for loop iterates size/2 times, and each iteration takes Theta(1) time. The remaining lines take Theta(1) time. So the overall complexity is Theta(size).