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 \(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