Running time/time complexity for while loop with square root

Question

This question looks relatively simple, but I can't seem to find the running time in terms of n.

Here is the problem:

j = n;
while(j >= 2) {
    j = j^(1/2)
}

I don't really need the total running time, I just need to know how to calculate the amount of times the second and third lines are hit (they should be the same). I'd like to know if there is some sort of formula for finding this, as well. I can see that the above is the equivalent of:

for(j = n; n >= 2; j = j^(1/2)

Please note that the type of operation doesn't matter, each time a line is executed, it counts as 1 time unit. So line 1 would just be 1 time unit, line 2 would be:

0 time units if n were 1,
1 time unit if n were 2,
2 time units if n were 4,
3 time units if n were 16, etc.

Thanks in advance to anyone who offers help! It is very much appreciated!

Wai Ha Lee · Accepted Answer · 2015-09-26 15:25:12Z

6

Work backwards to get the number of time units for line 2:

                                   time
n              n       log_2(n)    units
1              1        0          0
2              2        1          1
4              4        2          2
16             16       4          3
16^2           256      8          4
(16^2)^2       65536    16         5
((16^2)^2)^2)  ...      32         6

In other words, for the number of time units t, n is 2^(2^(t-1)) except for the case t = 0 in which case n = 1.

To reverse this, you have

t = 0 when n < 2

t = log₂(log₂(n)) + 1 when n >= 2

where log₂(x) is known as the binary logarithm of x.

edited Sep 26, 2015 at 15:25

answered Sep 26, 2015 at 14:45

Wai Ha Lee

8,856102 gold badges61 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Running time/time complexity for while loop with square root

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related