ALGORITHMS AND COMPLEXITY
HIT 220 Algorithms and Complexity Week 2 – Tutorial
COMPLEXITY CALCULATIONS
QUESTION 1
Suppose a computer takes 1 microsecond (a millionth of a second) to execute each operation.
How long will it take for the computer to execute each of the following numbers of operations?
(a) 200log 2
(b) 200
(c) 200log200 2
(d) 2
200
(e) 3
200 (f) 200
2
QUESTION 2
For each of the following algorithm segments, assume that n is a positive integer and
1. Compute the number of additions, subtractions, multiplications, divisions, and comparisons
that must be performed when the algorithm segment is executed;
2. State the order of complexity using big O notation.
(a) for 3:i to 1n
1.2.3: ina
next i
(b) ]1[:max a
for 2:i to n
if ][max ia then ][:max ia
next i
(c) for 1:i to 2n
ina :
next i
(d) for 1:i to n
for 1:j to n2
jina .: 2
next j
next i
(e) for 1:k to 1n
][:max ka
for 2: ki to n
if ][max ia then ][:max ia
next i
next k
HIT 220 Algorithms and Complexity Week 2 – Tutorial
(f) for 1:i to n
for 1: ij to n
if ][][ iaja then do
][: iatemp
][:][ jaia
tempja :][
end do
next j
next i
(g) for 1:i to n
for 1:j to 2)1( i
jina .: 2
next j
next i
QUESTION 3
Given that 32.310log 2
and 10log.)10(log 22 a a for all real numbers a, calculate:
(a) 000,1log 2
(b) 000,000,1log 2
(c) 000,000,000,000,1log 2
QUESTION 4
Given your answers in Question 4, generalise your results and comment on the following:
(a) Consider n 2
log . If we square n, by what factor does n 2
log increase?
(b) By what factor does n 2
log increase if we raise n to the tenth power.
(c) When n is increased from 100 to 10,000,000,000, by what factor is n 2
log increased?