I'm trying to figure out the runtime complexity of Lemke's algorithm for solving linear complementarity problems (LCPs). I've got a simple implementation going from the paper Linear Complementarity and Mathematical (Non-linear) Programming.

In general, I know the worst case complexity is exponential and average case complexity is polynomial. But I'm wondering if the matrices being, say, positive semi-definite changes the worst case complexity (say, because my matrices are built from an effective inverse mass matrix J*M-1*JT for instance ;)).

The actual algorithm has some O(n2) operation in the main loop body, so at best the worst case complexity is at least O(n3). I'm just wondering if that's a (provably) tight bound if you impose some additional requirements on the matrix.

Or if there's a reasonable argument that with practical problems from "real world" situations the chance of stumbling on a problem that gives exponential run time is vanishingly small, that would satisfy me too.