Let $A\in \mathbb{R}^{n\times n}$, symmetric and positive definite.  Suppose it takes $m$ units of work to multiply a vector by $A$.  It is well known that performing the CG algorithm on $A$ with condition number $\kappa$ requires $\mathcal{O} (m\sqrt{\kappa})$, units of work.Now, of course, being a $\mathcal{O}$ statement this is an upper-bound.  And the CG algorithm can always terminate in zero steps with a lucky initial guess.Do we know if there exists a RHS and an initial (unlucky) guess that will require $\mathcal{\Theta}(\sqrt{\kappa})$ steps?  Put another way, is worst-case work-complexity of CG really $\Theta( m \sqrt{\kappa})$?This question arises when I tried to determine if the benefit of a preconditioner (lower $\kappa$) outweighed its cost (higher $m$).  Right now, I am working with toy problems and would like to have a better idea before I implement anything in a compiled language.
What is the worst case complexity of Conjugate Gradient?
conjugate gradient