How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?
The loop iterates $k$ times, where $k$&nbsp;is minimal such that $\sum_{i=1}^k i&gt;n$.  We know that $\sum_{i=1}^k i = \tfrac12k(k+1)$, so you just need to solve for&nbsp;$k$.