# Derive a while loop runs in $\Theta( \sqrt{n} )$

I know for a fact that algorithm A runs in $$\Theta(\sqrt{n})$$, but how does one derive that fact?

Algorithm A

i = 0
s = 0
while s <= n:
s += i
i += 1


Here is what I am thinking. We know that A is upper-bounded by O(n), as we increment $$s$$ by more than 1 in each iteration. We also know that it must be lower-bounded by $$\log n$$, as we increment $$s$$ with by something less than $$2^i$$ in each iteration. (Correct me if I am wrong, these are just my thoughts ...).

Now, what else can we say about A? How do we derive that its time complexity is $$\Theta(\sqrt{n})$$?

Each time add $$i$$ to $$s$$ and increase $$i$$ by one, up to reach to $$n$$. Hence, if you find the $$k$$ such that $$s = 0 + 1 + 2 + ... + k$$ be equal to $$n$$, you can find the number of running loop. As $$1 + 2 + \ldots + k = \frac{k(k+1)}{2}$$, you need to solve this equation $$\frac{k(k+1)}{2} = n$$.

$$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \Theta(\sqrt{n})$$

After the first sqrt(n) iterations, s is increased by more than sqrt(n) in each iteration. Therefore at most 2 sqrt(n) iterations are needed to make s > n.

On the other hand, in the first sqrt(n) iterations, s is increased at most by sqrt(n) in each iteration, so sqrt(n) iterations are not enough.

This means the number of iterations is $$\Theta(n^{1/2})$$.

## Process of elimination

A, perhaps, easier method to derive the time complexity is by process of elimination. This is especially the case if you get this type of question in a multiple choice exam. That said, this method is far from as rigorous as OmG's answer.

Okay, we know that A is upper-bounded by O(n), as we increment $$s$$ by more than 1 in each iteration.

We also know that A must be lower bounded by $$\log n$$, as we increment $$s$$ by something less than $$2^i$$ each iteration.

Okay, so far so good.

Knowing our table of common time complexities, we can deduce that the time complexity of our loop must be either polylogarithmic time ($$(\log n)^2$$) or a fractional power. We now notice that we are not dealing with polylogarithmic time as that would imply having some variables doubbeling, for instance:

i = 1                // O( (log n)^2 )
while i ≤ n
j = i
while j ≤ n
j = 2 ∗ j
i = 2 ∗ i


, which is far from what we are dealing with, so we can eliminate this possibility.

... We are left with one possibility: a fractional power, aka. a squareroot of some sort.