It basically comes down to scaling with the size of the system, which will correspond to the number of electrons (that is, occupied valence orbitals) and the size of the basis set (which must have a sufficient quality, that is, size to yield meaningful results).
Edit: I should note that not all quantum chemists consider DFT to be ab-initio. Given the prevalence of such calculations, I have included it in my answer.
Let's consider density-functional theory (DFT) and Hartree-Fock (HF) theory first. These are a ground-state methods that describe a system with a single "wave function" called a Kohn-Sham or Slater determinant, respectively. This is valid for many, but not all systems - especially when there are several d-block metals closely interacting, this can be a bad approximation. For DFT, the cheapest useful specific methods (called functionals) in the most common implementations (i.e. programs) will scale as $\mathcal{O}(N^3)$ (where $N$ is some measure of the system size) due to the calculation of the electron-electron interaction.$^1$ At some point, a matrix diagonalization is performed, which has the same scaling. For HF, the scaling is worse, because of the calculation of a term called exchange (that arises from the specific form of the wave function ansatz), which scales as $\mathcal{O}(N^4)$.
At this point, I should mention that efforts to lower the prefactor of the computational cost function of these workhorses of quantum chemistry are ongoing and some have reached maturity. For "small" systems, the cost is then often dominated by terms other than the highest scaling ones. However, you will eventually hit the scaling wall. There are also efforts to lower the scaling behavior by introducing more approximations, smarter discarding of near-zero terms etc. Again, you may find out the hard way, that in the system you wish to calculate, the approximations do not hold or are not effective.
For excited states, one can assume a $+1$ scaling behavior and a worse prefactor. When considering the ground state with more accuracy, one then turns to post-DFT methods such as double-hybrid density functionals or post-HF methods such as Configuration Interaction, Møller–Plesset perturbation theory, Coupled-Cluster theory (e.g. CISD, MP$n$, CCSD(T)). In the standard implementations, they scale at least as $\mathcal{O}(N^5)$, but can go up to 6 and 7. Again, smart selection of the involved terms can lead to significant speed-ups, leading to an empirical linear or near-linear scaling at the expense of increased prefactors and less certainty.
The comments to the question mention classical dynamics of proteins. The scaling wall even for a single-point energy is hit well before approaching 100 $\ce{CNO}$ atoms (in my personal experience, which is a bit dated. Make it 200, then). The necessary derivatives with respect to the nuclear coordinates also tend to add to the prefactor or the scaling in a significant fashion.
$^1$ This scaling applies if a particular additional approximation called density fitting is made, which is usually a very good one. Note that better DFT methods will have worse scaling.