## Description

1. (3 marks) Use the definition of “big Oh” to prove that 1

2n−1

is O(

1

n

).

2. (3 marks) Let f(n) and g(n) be positive functions such that f(n) is O(g(n)) and g(n) ≥ 1 for all

n ≥ 1. Using the definition of “big Oh” show that f(n) + k is O(g(n)), where k > 0 is constant.

Hints. Since f(n) is O(g(n)) then there are constants c

′ > 0 and integer n

′

0 ≥ 1 such that

f(n) ≤ c

′

g(n) for all n ≥ n

′

0

. Hence, f(n) + k ≤ c

′

· · ·. Also, recall that g(n) ≥ 1 for all n ≥ 1.

3. (2 marks) Use the definition of “big Oh” to prove that 1

n

is not O(

1

n2 ).

4. (4 marks) Consider the following algorithm for the search problem.

Algorithm triSearch(L, f irst, last, x)

Input: Array L storing integer values sorted in non-increasing order, index first of the 1st value

in L, index last of the last value in L, and integer value x.

Out: Position of x in L if x is in L, or -1 if x is not in L

if first > last then return -1

else {

numV alues = last − first + 1

third ← first + ⌊

numValues

3

⌋

if x = L[third] then return third

else if x < L[third] then return triSearch(L, f irst, third, x)

else {

twoT hird ← first + 2 × ⌊ numV alues

3

⌋

if x = L[twoThird] then return twoThird

else if x < L[twoThird] then return triSearch(L, third, twoT hird, x)

else return triSearch(L, twoT hird, last, x)

}

}

1

Prove that either (i) the algorithm terminates, or (ii) the algorithm does not terminate.

Note that to prove that the algorithm terminates you cannot just give an example and show

that the algorithm terminates on it; instead you must prove that when the algorithm is given

as input any array L as specified and any values first, last, and x, the algorithm will always

end.

However, to show that the algorithm does not terminate it is enough to show an example

for which the algorithm does not finish. In this case you must explain why the algorithm

does not terminate.

5. (4 marks) Consider the following algorithm.

Algorithm copies(L, n, x)

Input: Array L storing n > 0 integer values, and value x

Output: The number of copies of the value x stored in L.

if x = L[0] then c ← 1

else c ← 0

for i ← 0 to n − 1 do

if x = L[i] then c ← c + 1

return c

Note that this algorithm terminates, as the for loop is repeated only n times.

Prove that either (i) the algorithm outputs the correct answer, or (ii) the algorithm does not

output the correct answer.

To prove that the algorithm is correct you cannot just give an example and show that the

algorithm computes the correct output. You must prove that when the algorithm is given

as input any array L storing n > 0 integer values and any value x, the algorithm correctly

outputs the number of times that the value x appears in L.

However, to show that the algorithm is incorrect it is enough to show an example for which

the algorithm produces the wrong answer. In this case you must explain why the output

is incorrect.

6. (4 marks) Consider the following algorithm.

Algorithm duplicated(L, n)

Input: Array L storing n > 1 integer values

duplicateFound ← true

i ← 0

while duplicateFound = true do {

if L[i] = L[i + 1] then return true

else duplicateFound = false

if i < n − 1 then i ← i + 1

}

return duplicateFound

Compute the time complexity of this algorithm in the worst case. You must explain how you

computed the time complexity, and you must give the order of the complexity.

7. (2 marks) Optional question. Download from OWL 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

).

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, 10000.

LinearSearch for, input sizes n = 5, 10, 100, 1000, 10000, 100000.

Fill out the following tables indicating the running times of the algorithms for the above input

sizes. You do not need to include your code for the Search class.

n Linear Search

5

10

100

1000

10000

100000

n Quadratic Search

5

10

100

1000

10000

n Factorial Search

7

8

9

10

11

12

3