What is the exact number of loop iterations here and how do you find out?

def func(n):
  i = 4

  while i < n:

  i = i + 1

The solution says max(n-4,0) which is theta(n), but I am confused about how they reached this. I see it starts from 4 and can guess that this relates to the n-4, but would like to be sure.

  • $\begingroup$ Try writing out what happens with both i and n for n = {0, 1, 2, 3, 4, 5}. Is there a pattern? What happens if n <= 4? $\endgroup$ – Jacob Panikulam Mar 23 '17 at 15:50
  • $\begingroup$ loop breaks if n<=4 no? and i simply increments by 1 $\endgroup$ – soka Mar 23 '17 at 15:59
  • $\begingroup$ Right. So how many times does the code inside of the loop get run if n = 5? Do your old pal Jake a favor and try making a table. $\endgroup$ – Jacob Panikulam Mar 23 '17 at 16:10
  • $\begingroup$ maybe once no?? $\endgroup$ – soka Mar 23 '17 at 16:21
  • 2
    $\begingroup$ If the indentation in the code is significant for scope resolution (e.g 'Is this Python?'), then it will iterate forever if $n>4$, because the line $i = i + 1$ isn't inside the body of the $while$ loop. One has to be careful about such things. $\endgroup$ – PMar Mar 23 '17 at 17:56

It will iterate $n-4$ steps if $n>4$ . If $n\leq4$ there will be no iteration since the condition is not satisfied. The important thing is that the linear search runtime grows like the sequence size in the worst case. The notation we use for works like $c_1.n+c_2$ is Θ (n).

  • $\begingroup$ how did you find n-4? the answer is max (n-4 ,0 ) does 0 relate to when n <=4? ...what does the max mean $\endgroup$ – soka Mar 23 '17 at 16:24
  • $\begingroup$ It means there cannot be any negative number of iterations. $\endgroup$ – kntgu Mar 23 '17 at 16:26
  • $\begingroup$ the 0 means that? or max.. can there ever be a negative # of iterations?? $\endgroup$ – soka Mar 23 '17 at 16:34

Seeing that $i$ starts with 4 $i = 4$, if it was $i = 0$ the number of times the loop would execute was be $n$ times.

Let $A$ and $B$ be the iterations of $i$.

$A = { 0,1,2,3, ... , n-1 }$

$B = { 4,5,6,7, ... , n-1 }$

The size of the $A$ set is $n$, the $B$ set has the same components of $A$ minus 4 numbers ${( 0,1,2,3 })$ , therefore the size of $B$ is $n-4$.

For $n-4$ be $\theta(n)$ $\exists$ $c_1,c_2$ and $n_0$ such that, $c_1 . n \leq n-1 \leq c_2 . n$.

  • $\begingroup$ I don't understand what you mean by "Let $A$ and $B$ be the iterations of $i$", followed by "$A=0, 1, \dots$". i never takes the value 0. $\endgroup$ – David Richerby Apr 23 '17 at 10:17
  • $\begingroup$ Just comparing, if $i$ started from 0. To show the difference between the size of the sets. $\endgroup$ – Vinícius G. Santos Apr 23 '17 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.