Description
1. (3 marks) Use the definition of “big Oh” to prove that 4/n is O(1).
2. (3 marks) Use the definition of “big Oh” to prove that 2n is not O(1/n).
3. (3 marks) Let f(n), g(n), and h(n) be non-negative functions such that f(n) is O(g(n)) and
g(n) is O(h(n)). Use the definition of “big Oh” to prove that f(n) + g(n) is O(h(n)).
4. Let A be an array storing n integer values. The goal is to design an algorithm that returns
true if every value stored in A is different, and it returns false if there is at least one value that
appears at least twice in A.
For example, for the following array A the algorithm must return true as all values are different;
however for array B it must return false as the values 3 and 4 appear twice.
3 6 1 7 2 4 5
0 1 2 3 4 5 6
A
2 3 1 4 4 3
0 1 2 3 4 5
B
• (4 marks) Write pseudocode for an algorithm as described above.
• Prove that your algorithm is correct:
(a) (1 mark) Show that the algorithm terminates.
(b) (2 marks) Show that the algorithm always produces the correct answer.
• (1 mark) Explain what the worst case for the algorithm is.
1
• (3 marks) Compute the time complexity of the algorithm in the worst case. You must
give the order of the time complexity using “big-Oh” notation and you must explain how
you computed the time complexity.
5. (2 marks) Optional question. Download from the course’s website:
http://www.csd.uwo.ca/Courses/CS2210a/
the java class Search.java, which contains implementations of 3 different algorithms for solving
the search problem:
• LinearSearch, of time complexity O(n).
• QuadraticSeach, of time complexity O(n
2
).
• FactorialSearch, of time complexity O(n!).
Modify the main method so that it prints the worst case running times of the above algorithms
for the following input sizes:
• FactorialSearch, for input sizes n = 5, 8, 9, 10, 11. If you dare, run the algorithm for
n = 12.
• QuadraticSeach, for input sizes n = 5, 10, 100, 1000, 2000.
• LinearSearch for, input sizes n = 5, 10, 100, 1000, 2000, 10000.
Print a table indicating the running times of the algorithms for the above input sizes. You do
not need to include your code for the Search class.
2
