Exact amount of loop iterations here? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:14:16Z https://cs.stackexchange.com/feeds/question/71945 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/71945 1 Exact amount of loop iterations here? soka https://cs.stackexchange.com/users/68250 2017-03-23T15:31:56Z 2017-04-22T23:16:51Z <p>What is the exact number of loop iterations here and how do you find out?</p> <pre><code>def func(n): i = 4 while i &lt; n: print(i) i = i + 1 </code></pre> <p>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. </p> https://cs.stackexchange.com/questions/71945/-/71947#71947 1 Answer by kntgu for Exact amount of loop iterations here? kntgu https://cs.stackexchange.com/users/68202 2017-03-23T16:11:47Z 2017-03-23T16:11:47Z <p>It will iterate $n-4$ steps if $n&gt;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).</p> https://cs.stackexchange.com/questions/71945/-/74385#74385 -1 Answer by Vinícius G. Santos for Exact amount of loop iterations here? Vinícius G. Santos https://cs.stackexchange.com/users/70918 2017-04-22T23:16:51Z 2017-04-22T23:16:51Z <p>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. </p> <p>Let $A$ and $B$ be the iterations of $i$.</p> <p>$A = { 0,1,2,3, ... , n-1 }$</p> <p>$B = { 4,5,6,7, ... , n-1 }$ </p> <p>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$.</p> <p>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$.</p>