It increments i
until i³
is greater than n
. Therefore i-1
will be floor(cube_root(n))
, and that's what's returned.
The running time is proportional to the cube root of n
, since that's how many iterations of the loop are performed.
Вопрос
could somebody please shed some light on what this piece of code is actually doing? I think it should be fairly straightforward but I am stuck at the moment, so any help would be greatly appreciated!
read n;
i := 1;
while (i * i * i) <= n do
i := i + 1;
output (i-1)
Also how could one calculate the complexity of this? Thank you in advance!
Решение
It increments i
until i³
is greater than n
. Therefore i-1
will be floor(cube_root(n))
, and that's what's returned.
The running time is proportional to the cube root of n
, since that's how many iterations of the loop are performed.