Numerical complexity of different quantum chemistry approaches For the introductory course for the students I am trying to collect the brief overview of different quantum chemistry methods and their numerical complexity. The second point is surprisingly poorly explained in all textbooks I was able to find. In the best case, it is a small note like

The most computationally expensive step in the Hartree–Fock procedure is the  formation of the two-electron part, $G$, of the Fock matrix; the computation of G requires $O(n^4)$ steps, where $n$ is the number of basis functions (with integral screening this cost asymptotically approaches $O(n^2)$) 

[source is "Parallel computing in quantum chemistry" by C.L. Janssen, 2008], but there are no estimates for all methods discussed in the book and I have problems to find this kind of information elsewhere. 
Probably, there exists a more extended discussion of this point with more details (which part of the algorithm limits the complexity, what can be done to improve the scalability, etc.)? 
 A: Because different computational methods require somewhat different expertise, it seems to me that, for each and every method, complexity/computational cost is commented separately. Therefore the exact details needs to be investigated maybe from books dedicated to a particular computational method. But of course there are some experts in the field who collectively reported these data.
The first and the most recent paper I found has a paragraph where data for different methods are presented without any discussion.

... the scaling of other popular Quantum Chemistry methods, which ranges from $O(N^4)$ for Hartree Fock (HF) to $O(N^5)$ for MP2, $O(N^6)$ for MP3, and $O(N^7)$ for MP4, CISD(T) and CCSD(T), it still makes large scale simulations prohibitive.

There is another paper I found which is relatively old (1996) but the discussion is more thorough and the data is given on a table very nicely.
 
A: For your basic single-reference quantum chemistry ground state methods:
HF: ${\cal O}(N^4)$
DFT: ${\cal O}(N^3)$ or ${\cal O}(N^4)$ with HF-exchange
MP2: ${\cal O}(N^5)$
CCSD: ${\cal O}(N^6)$
and excited state methods:
TDHF: ${\cal O}(N^4)$
TDDFT: ${\cal O}(N^3)$ or ${\cal O}(N^4)$
$\mathrm{G}_0\mathrm{W}_0$: ${\cal O}(N^4)$
GW: ${\cal O}(N^5)$
EOMCCSD: ${\cal O}(N^6)$
It's probably more useful to know why these methods come with the aforementioned cost scalings. It's all about identifying the rate-limiting step in the calculation, which is typically a type of tensor contraction. Let's take Hartree-Fock for example. The most costly step comes from the construction of the effective one-body interaction, which for a conventional closed-shell calculation, looks like this
$$f_{\mu \nu} = 2h_{\mu \nu} + g_{\mu \nu}$$
$$g_{\mu \nu} =  \sum_{\rho \sigma} \langle \mu \rho | \nu \sigma \rangle P_{\rho \sigma} - 
\frac{1}{2}\langle \mu \rho | \sigma \nu \rangle P_{\rho \sigma}$$
We can identify the first term in $g_{\mu\nu}$ as the Coulomb interaction and the second term as exchange. If one were to unravel the above tensor contraction to execute using some nested do/for loops, one would need something like this (using Fortran 90 as an example syntax):
do p = 1,N
    do q = 1,N
       K = 0.0
       J = 0.0
       do r = 1,N
          do s = 1,N
             K = K + V(p,q,r,s) * P(q,s)
             J = J + V(p,q,s,r) * P(q,s)
          end do
        end do
        g(p,q) = 2*K + J
    end do
end do

Clearly, the above loop has a computational expense that scales as $\mathcal{O}(N^4)$ because we have 4 nested loops, each running from $1$ to $N$. Another example we can do is CCSD. If you derive the CCSD equations (in spinorbital form for simplicity), one finds that the most expensive term is the so-called ladder diagram contribution $
\frac{1}{4}\sum_{mnef} v_{mn}^{ef} t_{ef}^{ij} t_{ab}^{mn}$ where $v_{pq}^{rs}$ are the antisymmetrized electron repulsion integrals and $t_{ab}^{ij}$ are the 2-body cluster amplitudes. If we were to repeat the above procedure of naively unravelling into nested "do" loops, one find that the ladder diagram has a cost that scales as $\mathcal{O}(N^8)$. Why then is CCSD listed as $\mathcal{O}(N^6)$? The answer is that the tensor contraction can be broken up into two steps. If one first computes $\chi_{mn}^{ij} = \sum_{ef} v_{mn}^{ef} t_{ef}^{ij}$, this operation scales as $\mathcal{O}(N^6)$. Then, one computes $\sum_{mn} \chi_{mn}^{ij} t_{ab}^{mn}$ which also scales as $\mathcal{O}(N^6)$. Thus, you can compute the $\mathcal{O}(N^8)$ contraction at the cost of no more than multiple $\mathcal{O}(N^6)$ operations, hence CCSD scales as $\mathcal{O}(N^6)$! These types of time-saving factorizations are easily deduced by inspection of the diagrammatic form of these many-body equations (or, one can just look at the tensor equations directly, however, it's a bit harder that way). Optimal factorization is of utmost importance in any quantum chemistry code.
And you can also reduce the scaling of MP2, TDHF, and HF using density-fitting and Cholesky decompositions by an order of magnitude to ${\cal O}(N^4)$ and ${\cal O}(N^3)$, respectively. There are also density-fitting type speedups (called least-squares tensor hypercontraction, or LS-THC) that can be applied to coupled-cluster that reduce the scaling of CCSD to ${\cal O}(N^4)$ which is probably the best you can get. Certainly, every method can have its scaling reduced dramatically by introducing some kind of orbital localization because the steep scaling of quantum chemistry stems from the fact that even atoms far away from each other, say on opposite ends of a molecule, end up interacting because the standard MO basis used is delocalized. However, localization comes with a heavy cost of losing orthonormality, so it's generally tricky implement. Actually, a very promising class of methods are the rank-compression methods like Cholesky decomposition because you can very robustly reduce the time needed for rate-limiting tensor contractions while having a very controllable and systematic error - something most other "fast scaling" approaches do not have.
A: The following figure is showing some numerical complexity for different methods in electronic structure calculations.

For more details you can visit this link.
Here is an excellent website for computational chemistry.
