For the following code fragment:

i = 1;
s = 1;

while(s <= n) {
    s = s+i;

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.

  • $\begingroup$ @OmG Please avoid using complexity theory tags for algorithm analysis. The correct tag to use is runtime-analysis. $\endgroup$ – Raphael Feb 22 '18 at 16:13
  • $\begingroup$ 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! $\endgroup$ – Raphael Feb 22 '18 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})$.

  • $\begingroup$ Ah that makes sense, however would you know I could figure that out using series notation? and proving it mathematically $\endgroup$ – bigfocalchord Feb 22 '18 at 20:48
  • $\begingroup$ @dydxx it's updated. $\endgroup$ – OmG Feb 22 '18 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.