# Relating number of iterations to n

n = length of list with more than n > 0. index = 0 step = 1 while index < n: index = index + step step = step + 1 return

How many times will the loop iterate relative to n? I have calculated the number of iterations based on n for the first 21 items, and I am failing to see a pattern. I

(n,#iterations) (1,1), (2,2), (3,2), (4,3), (5,3), (6,3), (7,4), (8,4), (9,4), (10,4)

I am looking for a way to determine the number of loop iterations given a number n.

What if you had this code?

 index = 0 step = 1 while forever: index = index + step step = step + 1 print index return 

It would output: 1, 3, 6, 10, 15, ...

Lets call the sequence members above $s_i$ where $i$ is an index running from $1$ to $\infty$. So essentially you have to find a position in the above list such that in your code $n \le s_i$

If $n=1$, then this happens for $s_1$

If $n=2$, then this happens for $s_2$

If $n=3$, then this happens for $s_2$

If $n=4$, then this happens for $s_3$

Which is all consistent with what you found. So the key is to find an expression for $s_i$. I'll work out the case where $i$ is even, and let you work out the odd:

If $i$ is even then we're adding terms like $1 + 2 + 3 + 4$ for example. Group these as $(1+4) + (2+3) = 5 + 5 = 10$. You can do this in general and you'll have $i/2$ groups each adding to $i+1$ so $s_i = \frac{i}{2}(i+1)$. The argument for the odd case is similar.

Now using this information can you figure out how many steps will be required for length $n$? You'll probably have to use a floor or ceiling function.

• What i'm trying to find is the Ω run time of the worst case behaviour of this algorithm. I thought being able to explicitly express the run time of the loop in relation to n would help with this. Although I am not sure, now... very confused. – user139934 Apr 3 '14 at 0:17
• The run time is proportional to the number of times you transverse the loop, so you're on the right track. The other answer made the next step more explicit, so try to apply that. – Kai Sikorski Apr 3 '14 at 0:20
• Okay thanks! Sorry for asking so many questions. I am slightly confused when you say "if n = 2, then this happens for s_2" isn't s_2 = 3, how would 2 >= 3? – user139934 Apr 3 '14 at 0:33
• Oh youre right i did it wrong – Kai Sikorski Apr 3 '14 at 0:40
• Okay sorry should have been n<=s_i – Kai Sikorski Apr 3 '14 at 0:43

Each pass through the loop, index becomes the next triangular number: $1,3,6,10,15\dots$ On the $k^{\text{th}}$ pass, it is $\frac 12k(k+1)$ You are looking to solve $n=\frac 12k(k+1)$ for $k$ and round up. It is a quadratic equation.