[dragontamer]

> Thinking of it as adversarial implies thinking in terms of algorithms that dynamically produce the worst-case rather than trying to just identify a static worst-case that is specific to one solution.

I think your statement makes sense for say, Quicksort or simple Binary Trees. In this case, the worst-case scenario is a "simple" reversed list. (ex: sorting [5 4 3 2 1] into [1 2 3 4 5]).

The worst-case insertion into an AVL-balanced tree however is a "Fibonacci Tree". AVL trees have a strange property where sorted lists [1 2 3 4 5 6 7] or [7 6 5 4 3 2 1] actually leads to optimal balancing. The sequence for worst case insertion into AVL Tree is something like [1 2 3 4 5 1.5 6] (1.5 to prevent the far-left tree from being perfectly balanced, and then 6 further unbalances the far-right branches)

Some algorithms have very non-intuitive worst-case scenarios.