Complexity of the simplex algorithm What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?

How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in practice the simplex algorithm will run significantly faster than this for more standard problems.

How can I reason about the average complexity of a problem being solved using this method?

Any information or references are greatly appreciated!
The simplex algorithm indeed visits all $2^n$ vertices in the worst case (Klee &amp; Minty 1972), and this turns out to be true for any deterministic pivot rule. However, in a landmark paper using a smoothed analysis, Spielman and Teng (2001) proved that when the inputs to the algorithm are slightly randomly perturbed, the expected running time of the simplex algorithm is polynomial for any inputs -- this basically says that for any problem there is a "nearby" one that the simplex method will efficiently solve, and it pretty much covers every real-world linear program you'd like to solve.  Afterwards, Kelner and Spielman (2006) introduced a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.