The order of complexity of the Pascal code -- like n * log(n)....

[doktorwho]

Homework Statement

The kind of problems i we are currently dealing with in school are like this:

Find the order of complexity of the function

Homework Equations

3. The Attempt at a Solution [/B]
Im suppose to guess or calculate the complexity of this based on code sample. Its in Pascal and to clarify what is meant here here is an example of the code and its complexity

for k:=1 to n do
   while x>0
      k:=k+1
      x:= x DIV 2

The complexity of this code is $n*logn$. The k-part is repeated n times while the inner while repeats logn times. How to solve these kinds of problems? What would be the best way?
As i see this, the i<n part is repeated n times, but the s-part confuses me. I can't see $2^n$

 

[mfb]

It will help if you look at the first 3 runs through of the outer loop manually. What happens to s in each step? How is that linked to the total iterations in the inner loop?

 

[doktorwho]

It will help if you look at the first 3 runs through of the outer loop manually. What happens to s in each step? How is that linked to the total iterations in the inner loop?

In the first run s is 1 and it is assigned to k. Then the inner code runs once, increases k by one and assigns it to s. Then the outer again assigns so to k but now the inner runs twice and increases k by 2. In the next run s is 8. Is that the pattern, then it will be 16 and it runs n times since the outer checks for i<n and it is increased by 1 every time?

 

[mfb]

The values used for s and k double every time, and they will do that n times, right.

That should lead to the number of steps done in the inner loop.