What is the computational complexity of Spectrum Estimation Algorthms and What they depend upon?
The computational requirements for various non-parametric PSD estimation methods is discussed in [*]. The complexity depends on the length $N$ of your data record. Roughly speaking:


The most straightforward periodogram method which calculates the magnitude squared of the DFT of $N$ samples has a complexity of $N \log N$.
Bartlett and Welch methods use $M$ overlapping windows of length $M$ each and calculate ~$N/M$ DFTs, so the complexity is $\frac{N}{M} \cdot M \log M = N \log M$.
Yule-Walker method for an $AR(p)$ inverts a $p\times p$ Toeplitz matrix which has a complexity of $O(p^2)$. The Toeplitz matrix itself is formed from estimates of the autocorrelation values calculated at $p$ different lags from the $N$-long data vector giving a complexity $O(Np)$. So the total complexity is $O(p^2 + Np)$.
MUSIC estimates an $M \times M$ autocovariance matrix from data by averaging the outer products of, say, $N/M$ $M$-long blocks of the original $N$-long signal and then calculates the eigendecomposition of the $M\times M$ autocovariance matrix which is $O(M^3)$. ($M$ is chosen by the user. For a signal with $p$ frequency components, choose $M&gt;p$.)


I don't think the complexity is affected by input noise level because the algorithms themselves do not change.

Reference

[*] J. Proakis Digital Signal Processing, 4th Edition Ch. 14 
https://www.pearsonhighered.com/program/Proakis-Digital-Signal-Processing-4th-Edition/PGM258227.html