Welcome file

tin093_as1_1.md

TIN093 Assignment 1

Danqing Li - 950121-C669 Robert Grzelka - 911009-T437

1.1. Complexity analysis of prime(n):

In the basic programming course (at least on Physics dept.) there has been a programming assignment where you generate all primes between 2..n. One simple way of doing it is to use Eratosthenes sieve:

• create an array 2..n filled with “true” booleans.
• traverse the array and change all (elements whose indexes are) multiples of 2 to false,
• traverse once more and change all multiples of 3 to false,
• then multiples of 5 and so on up till n.
• the primes corresponds to the true values left in the array.

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 7^2 = 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 loop

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?

prime: array [1..n] of boolean = all true
for p in 2..sqrt(n) loop                              
    if prime[p] then                                    
        for m = p*p; m<=n; m=m+p       
            prime[m] = false
        end loop
    end if
end loop

A trivial upper bound is $O(n^2)$ (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)

You should set up the sums and solve them. Don't forget to motivate what you do.

Analysis:

• Outer loop iterates from 2 to sqrt(n), so its simple $O(sqrt(n))$
• Inner loop iterates with some case for ie. n = 200:
  • p = 2 ::: m = [ 4, 6, 8, 10, 12, 14, 16, 18, 20, .... , 194, 196, 198, 200, ] ---> j=99, k=99
  • p = 3 ::: m = [ 9, 12, 15, 18, 21, 24, 27, 30, 33, ...., 195, 198 ] ---> j=64, k=163
  • p = 4 ::: m = [ ] ---> j=0, k=163
  • p = 5 ::: m = [ 25, 30, 35, 40, 45, 50, 55, 60, ...., 190, 195, 200 ] ---> j=36, k=199
  • p = 6 ::: m = [ ] ---> j=0, k=199
  • p = 7 ::: m = [ 49, 56, 63, 70, 77, 84, 91, 98, ...., 175, 182, 189, 196 ] ---> j=22, k=221
  • p = 8 ::: m = [ ] ---> j=0, k=221
  • p = 9 ::: m = [ ] ---> j=0, k=221
  • p = 10 ::: m = [ ] ---> j=0, k=221
  • p = 11 ::: m = [ 121, 132, 143, 154, 165, 176, 187, 198, ] ---> j=8, k=229
  • p = 12 ::: m = [ ] ---> j=0, k=229
  • p = 13 ::: m = [ 169, 182, 195, ] ---> j=3, k=232
  • p = 14 ::: m = [ ] ---> j=0, k=232
• with total number of (outer+inner) iterations: k = 232

In inner loop we see biggest number of iterations for p=2 at first case. Then it will drop almost by p, so complexity would be $O(n/p)$.

We need to find out how many times we add p to m until its $\leq$ to n (above this sum is in j counter at each inner for loop, so for n=200 : j = {99, 64, 36, 22, 8, 3}). We write equation:

$$ m = pp + jp \leq n \Rightarrow p*(p + j) = n $$

then

$$ \frac{n}{p} = p + j $$

and in converting to sum notation $\sum_{m=p}^{n/p}$, and assuming that $T(1)=1$ we will have double sum for outer and inner for loops :

$$ \sum_{p=2}^{\sqrt{n}}\sum_{m=p}^{\frac{n}{p}}1 $$

We also notice that:

$$ \sum_{j=m}^n 1 = n + 1 - j = n + 1 - m $$ so our inner sum will transform to: $$ \sum_{m=p}^{\frac{n}{p}}1 = \frac{n}{p}+1-p $$ Then our double sum equation becomes: $$ \sum_{p=2}^{\sqrt{n}}\left(\frac{n}{p}+1-p\right) $$ That we split on 3 parts: $$ \sum_{p=2}^{\sqrt{n}}\frac{n}{p} + \sum_{p=2}^{\sqrt{n}} 1 - \sum_{p=2}^{\sqrt{n}}p $$ With $\sum_{i=1}^N i = N*(N+1)/2$ this will converge to

$$ \sum_{p=2}^{\sqrt{n}}\frac{n}{p} + \left(\sqrt{n} + 1 - 2 \right) - \frac{\sqrt{n}}{2}(\sqrt{n} + 2) $$