Hardness of a subcase of Set Cover
When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$.

When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-hard. Given an instance of SET-COVER, add $m$ new elements $x_1,\ldots,x_m$ and $(2C^{-1}m)^2$ new sets, consisting of non-empty subsets of the new elements, including $\{x_1,\ldots,x_m\}$ (when $m$ is large enough, $(2C^{-1}m)^2 &lt; 2^m$). Also increase $k$ by one. The new $m,n$ are $m' = 2m$ and $n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$.