Asymptotically I can't see how you'd do any better than linear complexity in the number of visible polygons. You can certainly do worse. This code actually does a little worse because the complexity is linear in the number of polygons referenced by visible sectors, a bigger set. However I would hazard a guess that most other flash 3d engines (alternativa excluded) have frustum culling and backface culling but no occlusion culling. So they're higher still.
I would guess that the observations you've had without other engines (that they seem insensitive to size of the input) is more because they are doing some other large constant O(1) operation that is hiding the small constant O(N) complexity of drawing their triangles. Things like screenspace filtering, stage quality settings, motion blur... that kind of stuff. I try not to do that stuff very much. (Only the transparency textures, underwater distortion and zbuffer composition are those kinds of operations, and they were profiled and implemented carefully).
With the drawing turned off, the code (which is then just a physics simulation) will run very fast (100-200 fps+). When you shoot some grenades or whatnot, then it'll drop again. Nothing in life is free I guess :faded:
