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 operations into total work, where is the element count?
Sign in to answer questions and track your progress
Sign In