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 \

## Share on Social Media