Recovery of an $N$-dimensional, $K$-sparse solution $\mathbf{x}$ from an $M$-dimensional vector of measurements $\mathbf{y}$ for multivariate linear regression can be accomplished by minimizing a suitably penalized least-mean-square cost $||\mathbf{y}-\mathbf{H} \mathbf{x}||_2^2+λV(\mathbf{x})$. Here $\mathbf{H}$ is a known matrix and $V(\mathbf{x})$ is an algorithm-dependent sparsity-inducing penalty. For `random' $\mathbf{H}$, in the limit $λ\rightarrow 0$ and $M,N,K\rightarrow \infty$, keeping $ρ=K/N$ and $α=M/N$ fixed, exact recovery is possible for $α$ past a critical value $α_c = α(ρ)$. Assuming $\mathbf{x}$ has iid entries, the critical curve exhibits some universality, in that its shape does not depend on the distribution of $\mathbf{x}$. However, the algorithmic phase transition occurring at $α=α_c$ and associated universality classes remain ill-understood from a statistical physics perspective, i.e. in terms of scaling exponents near the critical curve. In this article, we analyze the mean-field equations for two algorithms, Basis Pursuit ($V(\mathbf{x})=||\mathbf{x}||_{1} $) and Elastic Net ($V(\mathbf{x})= ||\mathbf{x}||_{1} + \tfrac{g}{2} ||\mathbf{x}||_{2}^2$) and show that they belong to different universality classes in the sense of scaling exponents, with Mean Squared Error (MSE) of the recovered vector scaling as $λ^\frac{4}{3}$ and $λ$ respectively, for small $λ$ on the critical line. In the presence of additive noise, we find that, when $α>α_c$, MSE is minimized at a non-zero value for $λ$, whereas at $α=α_c$, MSE always increases with $λ$.