How to prove that the time complexity of this algorithm is O($\sqrt{N}$)? int n;
  cin &gt;&gt; n;
  int sum = 0;
  for (int i = 1; sum &lt;= n; i++) {
      sum += i;
  }


If I assumed that $N = 100$, the loop will run $13$ steps, which is almost the square root of $N$, if $N = 10000$, the loop will run $141$ steps, which is almost the square root of $N$, but I don't know how to prove that, I only know it by intuition
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$.