1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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})$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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