Worst-case performance describes the time, memory, or other resources an algorithm may use on its least favorable input of a stated size. Say what size means: a tree operation might depend on tree height rather than node count. Also say which resource and which operation the bound describes; a time bound does not describe extra memory. section 1.1
A costly dequeue
An immutable queue can use one stack for enqueues and another for dequeues. Most dequeues pop an item in O(1) time. When the dequeue stack runs out, reversing an enqueue stack of n items takes O(n) time and space. That is the worst case for one Dequeue, even though Enqueue takes constant time and memory. section 2.4
Does that make the queue slow overall? Not necessarily. Each item is pushed and popped only a constant number of times on its way through the queue, so enqueuing and eventually dequeuing items has O(1) amortized cost per item. The expensive reversal is followed by cheap dequeues—provided those calls continue from the resulting queue state. section 2.4 section 2.6.3
When the expensive call repeats
Enqueue 100 items, dequeue once, then undo to the earlier queue state. Repeating the dequeue reverses the same 99-item stack again. Undo prevents the later cheap dequeues from paying for that work. If this matters in practice, options include a data structure with a cheaper worst case or memoizing the reversal at a memory cost. section 2.6.3
Worst-case bounds also expose costs hidden by an algorithm’s apparent simplicity:
- A recursive change-ringing generator changes one pair between permutations, yet enumerating one n-element result can make up to n nested calls per element: O(n²) worst-case time. An O(log n) immutable-deque InsertAt could reduce this to O(n log n) per permutation. section 6.2.4
- Generating the next lexicographic permutation can require O(n) comparisons and swaps in the worst case. Most calls are much cheaper; across all permutations of unique items, the amortized cost is O(1) per permutation. section 6.2.1
A better asymptotic worst case is not automatically the better practical choice. A naïve string search with an O(n²) worst case can still be fast for the short searches typical of its intended use. Check the expected input sizes and common cases alongside the bound. section 1.1
Listing 6.12 A recursive change-ringing algorithm
static IEnumerable<IEnumerable<int>> Changes(int n)
{
if (n == 0) #1
{
yield return [];
yield break;
}
bool fromLeft = false; #2
foreach (var perm in Changes(n - 1))
{
for (int row = 0; row < n; row += 1)
yield return perm.InsertAt(fromLeft ? row : n-row-1, n-1);
fromLeft = !fromLeft; #3
}
}
static class Extensions
{
public static IEnumerable<T> InsertAt<T>(
this IEnumerable<T> items, int index, T insert)
{
int current = 0;
foreach (T item in items)
{
if (current == index)
yield return insert;
yield return item;
current += 1;
}
if (current == index)
yield return insert;
}
}
The C# change-ringing generator uses recursive permutations and InsertAt; enumerating the nested sequences reveals why producing one result can cost O(n²). section 6.2.4
