# Complexity of while loop using series

For the following code fragment:

i = 1;
s = 1;

while(s <= n) {
i++;
s = s+i;
printf("x");
}


How can we go about proving the time complexity of this code is $\Theta(\sqrt{n}))$?

Usually, I use sigma series analysis to figure the time complexity but I am having trouble turning this code into series notation and then using the series to find out the time complexity.

• @OmG Please avoid using complexity theory tags for algorithm analysis. The correct tag to use is runtime-analysis. Feb 22, 2018 at 16:13
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Feb 22, 2018 at 16:13

As you see, in each iteration i is increased by 1. Hence, value of s would be $1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, \ldots, \sum_{i=1}^{k}= n$
Hence, $k$ is the time complexity of this code. As we know that $\sum_{i=1}^{k} = \frac{k(k+1)}{2} = \Theta(k^2)$, and $\Theta(k^2) = n$, we can conclude that $k = \Theta(\sqrt{n})$.