I am trying to find some reasonable upper bound on $$\sum_k [0 < k\alpha \leq n] [\{k\alpha\} < 1/k]$$ where $\alpha$ is irrational, the brackets are Iverson's notation ($1$ if true, $0$ if false), and $\{x\} = x - \lfloor x \rfloor $. If we select an $n$ at random it will satisfy $\{n\alpha\} < 1/n$ about 1 in $n$ times so the summation might grow similar to $\sum_{k=1}^{\lfloor n/\alpha\rfloor} 1/k$.
I looked at the simpler case $$ S = \sum_k [0 < k\alpha \leq n] [\{k\alpha\} < \epsilon]$$ where $ 0 < \epsilon < 1$ and found
\begin{align} S &= \sum_{j,k} [0<k\alpha \leq n][k\alpha - \epsilon < j][j = \lfloor k \alpha \rfloor] \\ & =\sum_{j,k} [0<k \alpha \leq n] [k\alpha - \epsilon <j][j\leq k\alpha < j+1] \\ & =\sum_{j,k} [0<k \alpha \leq n][j \leq k\alpha < j + \epsilon] \end{align}
If $j \leq k\alpha < j+\epsilon$ and we search for the next $j$ and $k$, say $j+l_1 \leq (k+l_2)\alpha < j+l_1 + \epsilon$, and subtract we find $l_1 - \epsilon < l_2 \alpha < l_1 + \epsilon $. In other words if $l_1$ is the smallest natural number which satisfies this for some $l_2$ then all $j$'s which satisfy $j\leq k\alpha < j+\epsilon$ for some $k$ are at least $l_1$ apart. By fitting as many $j$'s as we can
\begin{equation} S \leq 1 + \left \lfloor \frac{\lfloor n/\alpha\rfloor - 1}{l_1}\right \rfloor \end{equation}
It also seems $l_1 \rightarrow \infty$ as $\epsilon \rightarrow 0$. The difficulty I've had with the first summation is $\epsilon$ is a function of $k$ which I haven't been able to handle.
Well, the short answer is "no". Your heuristic "If we select an $n$ at random it will satisfy $\{nα\}<1/n$ about 1 in $n$ times" is just plain wrong (while "if we select an $n$ at random it will satisfy $\{n\alpha\}<1/m$ about 1 in $m$ times" would be ok, that's what you feel yourself). If you had the condition $\{n\alpha\}<1/(3n),$ that might not be satisfied for any natural $n$, for some appropriate $\alpha$ ($\alpha=\sqrt2$ should turn the trick easily).
But you have $\{n\alpha\}<1/n$, and it's known there are infinitely many natural $n$ satisfying this, if $\alpha$ is irrational (it's a consequence of Dirichlet's approximation theorem). That doesn't mean the set of those $n$ is very dense. Let's investigate just the case $\alpha=\sqrt2$, to get some feeling for what to expect:
$\{n\sqrt2\}<1/n$ means that there is a natural $m$ with $$m<n\sqrt2<m+\frac1n,$$ i.e. $$-\frac1n<m-n\sqrt2<0.$$ Multiplying by $m+n\sqrt2$ and using $m<n\sqrt2,$ we obtain $$-2\sqrt2<m^2-2n^2<0.$$ Since $m^2-2n^2$ is an integer, we must have $$m^2-2n^2=-1$$ or $$m^2-2n^2=-2.$$ Both equations have (as it must be) infinitely many solutions $(m_k,n_k),$ given by $$m_k+n_k\sqrt2=(1+\sqrt2)(3+2\sqrt2)^k$$ for the first equation, and $$m_k+n_k\sqrt2=\sqrt2(3+2\sqrt2)^k$$ for the second one (let's cut a long story short, I can't explain the theory behind Pell's equations in a single answer). In both cases, $k\ge0.$ This shows that your original sum is indeed $O(\log n),$ but with a somewhat unexpected constant, I bet. And that's just the simple case of a quadratic irrationality, where we can make things explicit. It's far worse with $\alpha=\sqrt[3]2$ or (shuddering) $\alpha=\pi.$