Time complexity of nested while loop

Question

I am stumped on how to determine the time complexity for the while loop in this statement:

procedure P (integer n);
 for (i: 1 to n)
   x := n;
   while (x > 0)
         x := x - i;

I know that the for loop runs (n-1) times. At first I thought that the while loop would run n times because I mistook the i for a 1 but that is not the case. I have been inputting numbers to see when the program would stop, but do not see a consistent pattern. I noticed that as n increases, the while loop runs longer (but not by much) so could this be logarithmic somewhat? Thanks in advance.

MBo · Accepted Answer · 2016-10-18 07:13:46Z

5

The first run makes n while-cycles
The second run makes n/2 while-cycles
The third run makes n/3 while-cycles
k-th run makes n/k while cycles

So overall time is proportional to

n * (1/1 + 1/2 + 1/3 +...+1/n)

In the brackets we can see partial sum of harmonic series, that tends to natural logarithm of n, and complexity is O(n log n)

answered Oct 18, 2016 at 7:13

MBo

80.7k5 gold badges61 silver badges99 bronze badges

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

Comments

gbox · Accepted Answer · 2020-01-28 09:32:11Z

0

MBo answer is well detailed. If you got so far, maybe you are asking yourselves, why for the first run there are n while-cycles, second run n/2 while-cycles, etc.

     x := n;
     while (x > 0)
         x := x - i;

All cycles run until x==0 by the condition of the while loop

therefore the first while-cycle run: n-t*1=0 times for some integer t and i==1

the second while-cycle run: n-t*2=0 times for some integer t and i==1

So we get for the first one n=t for the second n=2tso n/2=t third n/3=t

answered Jan 28, 2020 at 9:32

gbox

8291 gold badge10 silver badges25 bronze badges

Collectives™ on Stack Overflow

Time complexity of nested while loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related