This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.
Group 7 consists of:
This hand in deals with complexity analysis of an algorithm \(prime(n)\), that works as follows:
prime: array [1..n] of boolean = all true
for p in 2..sqrt(n) loop
if prime[p] then
m = p*p
while m <= n loop
prime[m] = false
m = m+p
To make things more clear, we rewrote the algorithm so that it only uses for-loops.
The rewritten algorithm looks like:
#1 prime: array [1..n] of boolean = all true
#2 for p in 2..sqrt(n) loop
#3 if prime[p] then
#4 for m in p..n loop
#5 prime[m * p] = false
#6 end loop
#7 end if
#8 end loop
First things first, regarding line #1 - we couldn’t decide whether the array is an in-parameter and if the algorithm in that case begins by setting all elements in the array to true - in which case \(n\) would have to be added to \(T(n)\). In the section “Solving the sum” we haven’t added it, but it would be trivial to do so, and in the end it wouldn’t change the complexity class.
Let any constant initial cost of the algorithm be denoted \(a\). In this algorithm it is for example one might suspect that it would be the initialization of the for-loop at line #2.