Data Structures, Algorithms, & Applications in C++
Chapter 5, Exercise 25

The code is given below and in the file arrayListWithHalf.h. Test code is included in arrayListWithHalf.cpp. 
template<class T>
class arrayListWithHalf : public arrayList<T> 
{
   public:
      // constructor and destructor
      arrayListWithHalf(int initialCapacity = 10)
           : arrayList<T> (initialCapacity) {}

      void half();
};

template<class T>
void arrayListWithHalf<T>::half()
{// Remove all odd indexed elements.

   // move even indexed elements to new spots
   for (int i = 2; i < listSize; i += 2)
      element[i/2] = element[i];

   // destroy uneeded elements
   int newSize = (listSize + 1) / 2;
   for (int i = newSize; i < listSize; i++)
      element[i].~T(); 

   listSize = newSize;
}
Each for loop is iterated O(listSize) times. Each iteration of each loop takes O(1) time under the assumption that the complexity of the destructor for type T is O(1). Hence, the complexity of the function is O(listSize).