snippetMinor
How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?
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.