CSC165H1, Winter 2021 CSC165H1: Worksheet 16—Varying Loop Increments (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Analyse the running time of loops whose loop counter changes differently in different iterations.
• Analyse the running time of functions that call helper functions.
1. Varying loop increments. In lecture, we saw one example of a loop where the change to the loop variable was
not the same on each iteration. In this question, you’ll get some practice analyzing such loops yourself using a
general technique, which works when the loop condition is of the form i < x, where i is the loop variable and x is
some expression (e.g., n or n2). There are four steps:
(i) Identify the minimum and maximum possible change for the loop variable in a single iteration.
(ii) Use this to determine formula for an exact lower bound and upper bound on the value of the loop variable after
k iterations, say f1(k) ≤ ik ≤ f2(k).
(iii) Use these formulas and the loop condition to bound the exact number of loop iterations that will occur:
• For an upper bound on the number of iterations: find the smallest value k1 ∈ N that makes f1(k1) ≥ x.
Since ik1 ≥ f1(k1), the loop must stop after at most k1 iterations.
• For a lower bound on the number of iterations: find the smallest value k2 ∈ N that makes f2(k2) ≥ x.
Then at least k2 iterations must occur before the loop stops.
One subtlety with this technique is that a lower bound on ik determines an upper bound on the number of
iterations, and an upper bound on ik determines a lower bound on the number of iterations.
1
(iv) Conclude simple Big-O and Omega bounds on the running time. If you find the same expression for Big-O
and Omega, then you can also conclude a Theta bound.
(a) Note: we’ve omitted the conditions in the if, but assume they are constant time checks.
 def varying1(n: int) -> None:
 i = 0
 while i < n:
 if ...:
 i = i + 1
 elif ...:
 i = i + 3
 else:
 i = i + 6
Solution
The minimum change in the loop is that i increases by 1; the maximum change is that i increases by 6.
Let ik be the value of i after k iterations. The previous observation tells us that k ≤ ik ≤ 6k (these are
the lower and upper bounds on ik).
Part 1 (upper bound on running time).-
We want to determine a good upper bound (“at most ”) on the number of iterations that could
occur before the loop stops. Since the loop terminates when i ≥ n, we want to find the smallest value of
k such that ik ≥ n.
To do this, we use the lower bound on ik: since we know that ik ≥ k, if we pick k = n then this implies
ik ≥ n. This means that the loop can run at most n iterations. Since each iteration takes 1 step, this
loop takes at most n steps.
Counting 1 step for the line i = 0, the total number of steps is at most n + 1, which is O(n).
1Similarly, suppose we want to run 10km. A lower bound on our speed determines an upper bound on the time it will take to cover
the distance, and vice versa.
Page 1/5
CSC165H1, Winter 2021 CSC165H1: Worksheet 16—Varying Loop Increments (Partial Solutions)
Part 2 (lower bound on runtime).
Now we want to determine a good lower bound (“at least ”) on the number of iterations that must
occur before the loop stops. We find the smallest value of k that makes 6k ≥ n.
We can isolate k to obtain k ≥ n
6
, and since k is an integer, we can conclude k ≥
⌈n
6
⌉
. So at least
⌈n
6
⌉
iterations must occur.
Using a similar analysis as above, in total at least
⌈n
6
⌉
+ 1 steps occur, which leads to an asymptotic
lower bound o Ω(n).
Note: since the asymptotic upper bound and lower bounds are the same, we can conclude that the overall
running time of this function is Θ(n).
(b)
 def varying2(n: int) -> None:
 i = 1
 while i < n:
 if n % i <= i/2:
 i = 2 * i
 else:
 i = 3 * i
Solution
The argument is the same as the previous one, except now i increases by at least a multiplicative factor
of 2, and at most a factor of 3. This means that 2k ≤ ik ≤ 3k, and so the number of loop iterations is at
most dlog2 ne and at least dlog3 ne [using the same reasoning as in part (a)].
That is, the upper bound on the running time here is O(log2 n), and the lower bound is Ω(log3 n). Since
we know that log3 n ∈ Θ(log2 n), we can conclude that the tight bound on the running time is Θ(log n).
2. Helper functions. We have mainly analysed loops as the mechanism for writing functions whose running time
depends on the size of the function’s input. Another source of non-constant running times that you often encounter
are other functions that are used as helpers in an algorithm.
For this exercise, consider having two functions helper1 and helper2, which each take in a positive integer as
input. Moreover, assume that helper1’s running time is Θ(n) and helper2 is Θ(n2), where n is the value of the
input to these two functions.
Your goal is to analyse the running time of each of the following functions, which make use of one or both of these
helper functions. When you count costs for these function calls, simply substitute the value of the argument of the
call into the function f(x) = x or f(x) = x2 (depending on the helper). For example, count the cost of calling
helper1(k) as k steps, and helper2(2*n) as 4n2 steps.
(a)
 def f1(n: int) -> None:
 helper1(n)
 helper2(n)
Solution
The call to helper1 takes n steps, and the call to helper2 takes n2 steps, for a total of n2 + n steps.
This is Θ(n2).
(b)
Page 2/5
CSC165H1, Winter 2021 CSC165H1: Worksheet 16—Varying Loop Increments (Partial Solutions)
 def f2(n: int) -> None:
 i = 0
 while i < n:
 helper1(n)
 i = i + 2

 j = 0
 while j < 10:
 helper2(n)
 j = j + 1
Solution
The first loop takes
⌈n
2
⌉
iterations, and each iteration requires n steps for the call to helper1. As with
nested loops, we ignore the lower-order cost of the loop counter increment i = i + 2. So the total cost
of this loop is
⌈n
2
⌉
· n.
The second loop runs for 10 iterations, and each iteration requires n2 steps for the call to helper2. So
we count the cost for this loop as 10n2.
The total cost is
⌈n
2
⌉
· n + 10n2, which is Θ(n2).
(c)
 def f3(n: int) -> None:
 i = 0
 while i < n:
 helper1(i)
 i = i + 1

 j = 0
 while j < 10:
 helper2(j)
 j = j + 1
Solution
The first loop takes n iterations, but now the cost of the call to helper1 changes at each iteration. For
a fixed iteration of this loop, the cost of calling helper1(i) is i, and so the total cost over all iterations
of this loop is
n−1∑
i=0
i =
(n− 1)n
2
(note that this is the same as when we analysed one of the nested loop
examples from lecture).
Similarly, the cost of the second loop is
9∑
j=0
j2; this is one, however, is a constant cost with respect to n.
So the first loop has a running time of Θ(n2), and the second has a running time of Θ(1). The overall
running time is the sum of these two, which is Θ(n2).
Page 3/5
CSC165H1, Winter 2021 CSC165H1: Worksheet 16—Varying Loop Increments (Partial Solutions)
3. A more careful analysis. Recall this function from lecture:
 def f(n: int) -> None:
 x = n
 while x > 1:
 if x % 2 == 0:
 x = x // 2
 else:
 x = 2 * x - 2
We argued that for any positive integer value for x, if two loop iterations occur then x decreases by at least one.2
This led to an upper bound on the running time of O(n), but it turns out that we can do better.
(a) First, prove that for any positive integer value of x, if three loop iterations occur then x decreases by at least
a factor of 2. Note: this is an exercise in covering all possible cases; it’s up to you to determine exactly what
those cases are in your proof.
Solution
Proof. Let x0 be the starting value of x, and x1, x2, and x3 be the value of x after 1, 2, and 3 loop
iterations, respectively. We want to prove that x3 ≤ 1
2
x0. There are many ways of dividing this proof
into cases based on whether these values are even/odd. One simple approach is to look at the remainders
of x0 when dividing by 8; this has a lot of cases, but the calculation required for each case is pretty
straightforward. Here’s one as an example.
Case ??: assume x has remainder 5 when divided by 8, i.e., that there exists k ∈ Z such that x0 = 8k+5.
In this case, x0 is odd, and so Line 7 executes in the first loop iteration, making
x1 = 2x0 − 2 = 16k + 8 = 2(8k + 4)
So then x1 is even, and at the second loop iteration Line 5 executes, making
x2 =
1
2
x1 = 8k + 4 = 2(4k + 2)
So then x2 is even, and at the third loop iteration Line 5 executes again, making
x3 =
1
2
x2 = 4k + 2 =
1
2
x0 − 1
2
Therefore x3 ≤ 1
2
x0.
(b) For every k ∈ N, let xk be the value of the variable x after 3k loop iterations, in the case when 3k iterations
occur. Using part (a), find an upper bound on xk, and hence on the total number of loop iterations that will
occur (in terms of n). Finally, use this to determine a better asymptotic upper bound on the runtime of f
than O(n).
(Note: you might need to write your analysis on a separate sheet of paper.)
Solution
We showed in part (a) that after 3 iterations, the current value of x decreases by at least a factor of 2, or
the loop has terminated. So then for any k, either the loop terminates within 3k iterations, or the value
of x has decreased by at least a factor of 2k. Since x is initialized to n, we know that xk ≤ n
2k
.
The loop terminates when x ≤ 1, and this occurs when 2k ≥ n, i.e., k ≥ dlog ne. So then the loop will run
2We phrase this as a conditional because it might be the case that the loop stops after fewer than two iterations.
Page 4/5
CSC165H1, Winter 2021 CSC165H1: Worksheet 16—Varying Loop Increments (Partial Solutions)
for at most 3 · dlog ne iterations; since each iteration takes constant time, the total runtime is O(log n).
Page 5/5





























































































































































































































学霸联盟