1
$\begingroup$

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

def func(n):
  i = 4

  while i < n:
    print(i)

  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.

$\endgroup$
7
  • $\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$ Mar 23, 2017 at 15:50
  • $\begingroup$ loop breaks if n<=4 no? and i simply increments by 1 $\endgroup$
    – soka
    Mar 23, 2017 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$ Mar 23, 2017 at 16:10
  • $\begingroup$ maybe once no?? $\endgroup$
    – soka
    Mar 23, 2017 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, 2017 at 17:56

2 Answers 2

1
$\begingroup$

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).

$\endgroup$
3
  • $\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, 2017 at 16:24
  • $\begingroup$ It means there cannot be any negative number of iterations. $\endgroup$
    – kntgu
    Mar 23, 2017 at 16:26
  • $\begingroup$ the 0 means that? or max.. can there ever be a negative # of iterations?? $\endgroup$
    – soka
    Mar 23, 2017 at 16:34
-1
$\begingroup$

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$.

$\endgroup$
2
  • $\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$ Apr 23, 2017 at 10:17
  • $\begingroup$ Just comparing, if $i$ started from 0. To show the difference between the size of the sets. $\endgroup$ Apr 23, 2017 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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