Week 2

Question 1

You work for a small medicine stocker. Your boss comes and asks your opinion on which of two approaches is faster for employees to search over an unordered set of medicines (strings).

Which of the following two approaches will tell your boss is faster? (Bonus marks for big o notations)

• Sequential Search
• Sort then Search

Answer 1

Neither, both are okay.

If repeated use, sort then search.

Sort Search: C(n) = O(n^2)
Sequential Search: C(n) = O(n)

Question 2

What is a basic operation?

Answer 2

Operation that contribute most towards the total running time.

Typically the operation most frequently executed, although dependant on the time of each operation.

Question 3

Identify the basic operation in the following pseudo code:

set s = 1
for i = 1 to n do
   s = s * a
end for
return s

Answer 3

Multiplication

Comparison

Question 4

What is the basic running time estimation equation?

Answer 4

Running time approximately equal to time to execute a basic operation times number of basic operations:

t(n)≈Cop×C(n)

Question 5

Define Worst Case, Best Case and Average Case

Answer 5

Worst: Maximum running time
Best: Minimum running time
Average: Average running time

Question 6

For the following pseudo code, define the best, worst and average cases:

SequentialSearch(A[0...n-1], K)
set i = 0
while i < n and A[i] ≠ K do
   set i = i + 1
end while
return i

Answer 6

Best-Case = Cb(n) = 1
Worst-Case = Cw(n) = n

Where p = probability of key existing
Average-Case = Ca(n) = ((p(n+1))/2)+n(1-p)
∴ if p = 1, then Ca(n) = (n+1)/2
∴ if p = 0, then Ca(n) = n

Question 7

What does Omega or Big-O notation stand for?

Answer 7

Order of Growth. (Upper bound)

Formally: t(n) (running time) ∈ O(g(n)) if g(n) is a function and c x g(n) is an upper bound on t(n).

Question 8

Order the following bounds in terms of t(n), fastest to slowest.

O(n^2)
O(n)
O(1)
O(2^n)
O(n log n)
O(log n)
O(n!)

Answer 8

O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(2^n)
O(n!)

Question 9

Solve the equivalence function class for the following problem:

0.003n + n^3 -6

Answer 9

n^3