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

Question

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

Note that questions about theoretical computer science have their own Stack Exchange site, at [cs.se]; SO is narrowly focused on *writing code*, and tools exclusively for that use. — Charles Duffy, Sep 29 '19 at 17:32
@CharlesDuffy I find it a little perplexing how other questions regarding time complexity is warmly welcomed on SO, when mine is not. (eg. https://stackoverflow.com/q/2095395/7123519 (a lot more theoretical than my question)) — Sebastian Nielsen, Sep 29 '19 at 19:10
Our rules change over time -- and of course, some historical questions were added before [cs.se] existed at all. If you want an idea of current consensus, ask a question over on [meta], and feel free to link me to it; should there be a strong, current consensus there that questions about time complexity analysis are on-topic on SO proper, I'll honor it (as will others, when same is brought to attention). — Charles Duffy, Sep 30 '19 at 13:44

Massifox · Answer 1 · 2019-10-01T09:57:29.603

2

To help you in your reasoning you could do experimental tests to count the number of iterations. For example:

for n in range(100000000, 1000000000, 100000000) :   
    i = 0
    s = 0
    while s <= n:
        s += i
        i += 1

and get the following results:

    n       | iterations|   sqrt(n)
-------------------------------------
100000000   |   14143   |   10000.00
200000000   |   20001   |   14142.14
300000000   |   24496   |   17320.51
400000000   |   28285   |   20000.00
500000000   |   31624   |   22360.68
600000000   |   34642   |   24494.90
700000000   |   37418   |   26457.51
800000000   |   40001   |   28284.27
900000000   |   42427   |   30000.00

EDIT

As recommended by @WillNess You can learn more about it here

edited Oct 01 '19 at 09:57

answered Sep 29 '19 at 18:04

Massifox

4,369
11
31

1

cf. http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth – Will Ness Oct 01 '19 at 09:53
Thanks, I added your link to the answer @WillNess – Massifox Oct 01 '19 at 09:58

score 1 · Answer 2 · answered Sep 29 '19 at 18:17

As you can see from the code s = 1 + 2 + 3 + .... + i (1) and s <= n (2). The first equation can also be written as s = i * (i + 1) / 2 which means that in i is approximately sqrt(s * 2) and sqrt(n * 2), and as we see from the code the while loop runs i time, each does a O(1) calculation. Therefore the overall complexity is O(sqrt(n))

score 1 · Accepted Answer · edited Sep 29 '19 at 22:48

Each time we increment i, we add s to i. This thus means that after k steps, s has grown to:

     k
    ---
    \
s = /   i
    ---
    i=0

This sequence is known. After the k-th step, there are T_k numbers, with T_k a triangular number [wiki]. A shorter formula for T_k is T_k=i×(i+1)/2. T_k thus scales quadratic with k.

The process will thus stop when T_k is higher than n. We can thus determine that: T_k > n, and thus k×(k+1)/2 > T_k and thus k²/2 + k/2 - n > 0. This is a quadratic equation with as discriminant d = 1/4 + 2×n, and thus as (positive) solution k₀=-1/2 + √d. It thus scales with √2n.

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

3 Answers3

EDIT