ALGORITHMS AND COMPLEXITY

farhankhan

HIT220TutorialWeek2QuestionsonComplexity1.pdf

Home >Information Systems homework help >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) 200log2 (b) 200

(e) 3200 (f) 2002

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 1n

1.2.3:  ina

next i

(b) ]1[:max a

for 2:i to n

if ][max ia then ][:max ia

next i

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 1n

][: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.310log2  and 10log.)10(log 22 a a  for all real numbers a, calculate:

(a) 000,1log2 (b) 000,000,1log2

QUESTION 4

Given your answers in Question 4, generalise your results and comment on the following:

(a) Consider n2log . If we square n, by what factor does n2log increase?

(b) By what factor does n2log increase if we raise n to the tenth power.