Exercises
10.1. Exercises#
Many of these exercises are taken from past exams of ECE 244 Programming Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.
Headings in this page classify the exercises into different categories: [Easy], [Intermediate], and [Challenging]. I suggest you start by easy exercises and work your way up to the challenging ones.
Question 16 in Fall 2021 Final Exam [Intermediate]
For each code snippet, specify the worst case complexity using the Big-O notation.
for (int i = 0; i < n; i++) { for (int j = 0; j * j < n; j++) { // some code with o(1) } }
Answer
Think of it as \(n \times (j^2 < n \rightarrow j < \sqrt{n} = ) \sqrt{n} = n^\frac{3}{2}\)
\(O(n^\frac{3}{2})\)
for (int i = 0; i < n; i++) { for (int j = 0; j * j < 1000000; j++) { // some code with O(1) } }
Answer
Think of it as \(n \times 1000000 = n\)
\(O(n)\)
for(int i = 1; i < n ; i = i*2){ for(int j = 0; j < n; j++){ // some code with O(1) } }
Answer
The outer loop goes from 1, 2, 4, 8, 16 …
To reach \(n\), this takes \(\log(n)\) steps.
Think of it as \(\log(n) \times n\)
\(O(n\log(n))\)
Question 17 in Fall 2021 Final Exam [Intermediate]
Two students were asked to write a recursive function that given a positive integer n, computes \(2^n\). Amy wrote the following function:
int Amy(int n) {
if (n == 0) {
return 1;
} else {
return Amy(n - 1) + Amy(n - 1);
}
}
John wrote the following function:
int John(int n) {
if (n == 0) {
return 1;
} else {
return (2 * John(n - 1));
}
}
Answer the following question about code written by Amy and John.
Is Amy’s function correct (does it compute and return \(2^n\))?
Answer
Yes
Is John’s function correct (does it compute and return \(2^n\))?
Answer
Yes
What is the worst-case complexity of Amy’s function using Big-O notation?
Answer
\(O(2^n)\)
What is the worst-case complexity of John’s function using Big-O notation?
Answer
\(T(n) = T(n - 1) + c\)
\(T(n) = T(n - 2) + 2c\)
\(O(n)\)
In progress!