In order to know whether an arena is empty, you need to have walked, at a minimum, each object that was in the arena. That applies for copying collections too as during the copy phase you've walked and inspected each object that might be copied into the arena at least once. Arenas do not reduce the cost of garbage collection to O(1). And in any event arenas are not solely the preserve of sweeping or sweeping+copying collectors.

The algorithmic complexity of a sweeping collector is identical to that of a reference counting collector that can also break cycles. See A Unified Theory of Garbage Collection at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146....

A reference counting collector that _cannot_ break cycles (like in Swift) might have lower algorithmic complexity. I'm not sure.

The biggest bone of contention with reference counting is the constant adjustment of the reference count of objects on the stack. OTOH, the bone of contention with sweeping collectors is constantly walking all extant objects, including ones not directly on the stack.

There are various optimizations you can make to one or the other or both; many arguments about how real-world scenarios tax one or the other model; and many arguments about which is easier to optimize. But at the end of the day reference counting is no worse in terms of algorithmic complexity than sweeping. What matters most will be the quality of implementation. Is the compiler smart enough to know that an object passed 3 routines deep doesn't really escape the stack scope? If it can do that, it can elide all the cost of either approach.