xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CSC165H1

时间：2021-04-05

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

学霸联盟

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

学霸联盟