White RoomNEW White Room DSA

Thrashing At Half Full

An engineer adds shrinking to a dynamic array and picks the same threshold in both directions:

void resize(vec *v) {
  if (v->size == v->cap)            v->cap = v->size * 2;  /* grow   */
  else if (v->size * 2 <= v->cap)   v->cap = v->size;      /* shrink */
  else return;
  /* allocate cap slots, copy size elements, free the old block */
}

resize runs before every push and after every pop. Which workload turns mm operations into Θ(mn)\Theta(m \cdot n) total work, where nn is the element count?