What is the time complexity of conjugate gradient method?

Question

I have been trying to figure out the time complexity of the conjugate gradient method.

I have to solve a system of linear equations given by

$$Ax=b$$

where $A$ is a sparse, symmetric, positive definite matrix.

What would be the time complexity of the conjugate gradient method?

Answer 1

$O(m\sqrt{k})$, where $m$ is the number of nonzero entries in $A$ and $k$ is its condition number.

See Chapter 10 in this excellent tutorial.