# Introduction

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

Group 7 consists of:

• 901011-0279

• twingoow@gmail.com

• Program: IT

• 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 

# Analysis and setting up the sum

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 \