HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisthetimesqrtalgorithmprovethathowcomplexity

Problem

int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; sum <= 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

Solution

The loop iterates $k$ times, where $k$ is minimal such that $\sum_{i=1}^k i>n$. We know that $\sum_{i=1}^k i = \tfrac12k(k+1)$, so you just need to solve for $k$.

Context

StackExchange Computer Science Q#105873, answer score: 6

Revisions (0)

No revisions yet.