This is a hand-in written by **Group 7** (FIRE) for the Algorithms course (**TIN092**) at Chalmers University of Technology.

Group 7 consists of:

**Mazdak Farrokhzad**901011-0279

twingoow@gmail.com

Program: IT

**Niclas Alexandersson**920203-0111

nicale@student.chalmers.se

Program: IT

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
end loop
end if
end loop
```

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.

Ima

## Share on Social Media