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

Tags:
1. Jan 15, 2017

### doktorwho

1. The problem statement, all variables and given/known data
The kind of problems i we are currently dealing with in school are like this:

Find the order of complexity of the function
2. Relevant equations
3. The attempt at a solution

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
Code (Pascal):

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$

2. Jan 15, 2017

### Staff: Mentor

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?

3. Jan 16, 2017

### doktorwho

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?

4. Jan 16, 2017

### Staff: Mentor

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.