Algorithms - Lab 1, Problem 1

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:

  • 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

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 \