The main computational complexity of computing the conjugate direction lies in the calculation of the Riemannian gradient and the horizontal projection which requires \(O\left(d\vert \Omega \vert r^2+ dnr^6+d^3r^4\right)\)  flops.
Additionally, it takes \(O\left(d\vert \Omega \vert r^2\right)\)  flops to compute the step size \(\alpha _t\)  [1]}. Thus, if \(d^2\ll nr^2\) , the leading order per iteration computational cost of RCG (Q) is \( O \left(d\vert \Omega \vert r^2+dnr^6 \right)\) .
