I want to know the time complexity of inverting $K$, where $K$ is an positive-definite $n\times n$ matrix: $$K=\Lambda+Q$$, where $\Lambda$ and $Q$ are both $n\times n$ matrix, $\Lambda$ is a full-rank diagonal matrix and $Q$ has rank $m$.
Snelson claims that $K$ can be inverted in $\mathcal O(nm^2)$ (page 3). However, I tried Sherman-Morrison Formula and Woodbury formula and both result in $\mathcal O(n^2m)$. $$$$
- Sherman-Morrison Formula says $(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$
Let $Q=\sum_{i=1}^mu_iv_i^T$, where $u_i$ and $v_i$ are $n\times 1$ vectors, $i\in\{1,2,...,m\}$. Thus, $K=\Lambda+\sum_{i=1}^mu_iv_i^T$.
By Sherman-Morrison Formula, $$K^{-1}=(\Lambda+\sum_{i=1}^mu_iv_i^T)^{-1}\\=(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}+\frac{(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}u_mv_m^T(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}}{1+v_m^T(\Lambda+\sum_{i=1}^{m-1}u_iv_i^T)^{-1}u_m}$$
By doing so for $m$ times, $K^{-1}$ can be solved by calculating $\Lambda^{-1}$ and $u_iv_i^T$, $i\in\{1,2,...,m\}$. It's obvious that solving $\Lambda$ is easy for it's diagonal, but $u_iv_i^T$ costs $\mathcal O(n^2)$ since they are $n\times 1$ vectors. Overall, the total time complexity should be $\mathcal O(n^2m)$, not $\mathcal O(nm^m)$.$$$$
- Woodbury formula:$(A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}$, where $U$ is $n\times m$, $C$ is $m\times m$, and $V$ is $m\times n$.
Assuming that $Q$ can be decomposed into $UCV$ just like the $UCV$ above (please do not question the feasibility; it is true in my research area):$$K^{-1}=(\Lambda+UCV)^{-1}\\=\Lambda^{-1}-\Lambda^{-1}U(C^{-1}+V\Lambda^{-1}U)^{-1}V\Lambda^{-1}$$ $\Lambda^{-1}$ is diagonal so the time complexity can be ignored. $C^{-1}$ is $\mathcal O(m^3)$. Note that $\Lambda^{-1}U(C^{-1}+V\Lambda^{-1}U)^{-1}V\Lambda^{-1}$ eventually becomes matrix multiplication of $n\times m$ and $m\times n$ matrices, so the time complexity should be $\mathcal O(n^2m)$, not$\mathcal O(nm^2)$.
$$$$ Where did I go wrong, or there are still some tricks that can do $\mathcal O(nm^2)$?