Description
1. (3 marks) Use the definition of “big Oh” to prove that 3n
3
is O(n
4
).
2. (3 marks) Use the definition of “big Oh” to prove that n
3 + n
2
is not O(n
2
).
3. (3 marks) Let f(n) and g(n) be non-negative functions such that f(n) is O(g(n)) and g(n) is
O(f(n)). Use the definition of “big Oh” to prove that f(n) − g(n) is O(f(n)).
4. Let A and B be two arrays, each storing n different integer values. The goal is to design an
algorithm that returns true if A and B have no common values, and it returns false otherwise.
For example, if the algorithm receives as input below arrays A and B the algorithm must return
true as no value in A is also in B; however if the algorithm receives as input arrays A′ and B
it must return false as the values 3 and 4 in A′ also appear in B.
6 8 1 7 5
0 1 2 3 4
A
3 9 4 0 2
0 1 2 3 4
B
8 3 1 4 6
0 1 2 3 4
A′
i. (4 marks) Write pseudocode for an algorithm as described above. You cannot use a
hashmap or any other additional data structures. You cannot sort the arrays.
ii. 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.
iii. (1 mark) Explain what the worst case for the algorithm is.
1 CS 2210a
iv. (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 = 7, 8, 9, 10, 11, 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
