You are correct. For example the worst and average cases for the Simplex Method are dramatically different. However, in practice, complex Bayesian nets do win

You are correct. For example the worst and average cases for the Simplex Method are dramatically different. However, in practice, complex Bayesian nets do wind up being computationally intractable. Therefore attempts to build real world machine learning systems consistently find themselves going to computationally tractable heuristic methods with rather obvious failure modes.