1
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.