Group 1:
The complexity/speed of group 1. seems not too difficult to figure out if brute force algorithms are used (although there may be more efficient alternatives such as the "leaps and bounds" algorithm). For example, full subset selection will require $2^K$ regressions to be fit given a pool of $K$ candidate features. An OLS fit of one linear regression has the complexity of $\mathcal{O}(K^2 n)$ (as per this post) where $n$ is the sample size. Hence, the total complexity of brute-force full subset selection should be $\mathcal{O}(2^K K^2 n)$.
Group 2:
The complexity/speed of group 2. is discussed in sections 3.8 and 3.9 of the book. For example, ridge regression with a given penalty $\lambda$ has the same computational complexity as a regular regression. Since $\lambda$ needs to be found using cross validation, the computational load increases linearly in the number of data splits used in cross-validation (say, $S$). If the $\lambda$ grid has $L$ points, the total complexity of ridge regression with tuning the $\lambda$ parameter will be $\mathcal{O}(LSK^2 n)$.
There is quite some talk about LASSO in the book, but I could not find quite what I need. However, I found on p. 443 of Efron et al. "Least Angle Regression" (2004) that LASSO complexity for a given $\lambda$ is the same as the complexity of an OLS fit of linear regression if LARS method is used. Then the total complexity of LASSO with tuning the $\lambda$ parameter will be $\mathcal{O}(LSK^2 n)$. (I did not read that paper carefully, so please correct me if I got this one wrong.)
Elastic net combines ridge and LASSO; the two have the same computational complexity; hence, the complexity of elastic net should be $\mathcal{O}(ALSK^2 n)$ where $A$ is the grid size of the tuning parameter $\alpha$ that balances the weights of ridge versus LASSO.
Group 3:
I still miss any note on the complexity/speed for group 3. which consists of principal components regression (PCR) and partial least squares (PLS).
