NOTE: It is vital to solve problems in a course like this and I urge you to solve as many as possible. We have prepared several assignments with two problems each that you can hand in and get feedback on. But the assigments are optional, you can submit none, one or two of the problems. If you submit them we will grade them and give you feedback (and no bonuspoints are given for the exam).
This naive solution takes O(n2) time. The solution can be improved in several ways. It's for instance enough to try primes up to sqrt(n) instead of to n and if you are marking multiples of 7 it's enough to start from 72 = 49 because all multiples between 7 and 49 must be marked already.
An algorithm for the problem could look like this:
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 loopA trivial upper bound is O(n2) (or O(n*sqrt(n)) ) but empirical experiment (=running the program) suggest that the worst case complexity is even better. Analyse the program and determine it's complexity and show that it infact is better. (Use uniform cost criteria)
Tip: It's simpler to analyse if you rewrite the while loop to a for loop, then it's a double
sum isn't it?
How to handle the statement: "if prime(p)" in worst case?
You don't need to find the best complexity, you only need to show that it is better than O(n*sqrt(n)) so you could use "worst case" here and see what you get.
Answers should be written in English.