Warning! This is the 2012 course's website! You probably want the current course website.

Inlämningsuppgift 1: Komplexitet

Uppgifterna lämnas in som text- eller PDF-dokument via Fire. För deluppgift 2 bör ni också ge en kort förklaring till hur ni har fått fram komplexiteten.

Uppgifter

1. Fyll i tabellen nedan. För varje funktion f(n) och tid t skall ni bestämma det största storleken n som kan lösas under tiden t, där arbetet tar f(n) mikrosekunder.

   Två storlekar har redan beräknats, för att ni skall lättare komma igång. För den sista kolumnen ska ni använda summan av antalet år ni har levat totalt. Glöm inte att berätta era sammanlagda levnadsår, så att det går att rätta.

   f(n)	1 sekund	1 timme	1 månad	er sammanlagda levnadstid
   log2 n	ca 10300000
   √n
   n
   n log2 n
   n2
   n3
   2n
   n!		12

2. Vilken är komplexiteten för följande funktioner? Beskriv med en matematisk funktion hur antalet additionsoperationer beror på n, (vilket är detsamma som funktionsresultatet). Ange sedan ordo-funktionen.

   OBS! De tre sista funktionerna (Ex8, Ex9 och Ex10) är svåra att beräkna exakt! Så där räcker det med enbart ordo-funktionen som svar.

   public int Ex1(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       sum += 1;
     return sum;
   }
   
   public int Ex2(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       for (int j = 1; j < n; j++)
          sum += 1;
     return sum;
   }
   
   public int Ex3(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       sum += 1; 
     for (int j = 0; j < n; j++) 
       sum += 1; 
     return sum;
   }
   
   public int Ex4(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       for (int j = 1; j < n*n; j++)
          sum += 1;
     return sum;
   }
   
   public int Ex5(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       for (int j = 0; j < i; j++) 
         sum += 1; 
     return sum;
   }
   
   public int Ex6(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       for (int j = i+1; j < n; j++) 
         for (int k = j+1; k < n; k++) 
           sum += 1; 
     return sum;
   }
   
   public int Ex7(int n) {
     if (n > 0)
       return 1 + Ex7(n-1);
     else 
       return 0;
   }
   
   public int Ex8(int n) {
     if (n > 1)
       return 1 + Ex8(n/2);
     else 
       return 0;
   }
   
   public int Ex9(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) {
       sum += 1 + Ex9(n-1);
     return sum;
   }
   
   public int Ex10(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) {
       sum += 1 + Ex10(n/2);
     return sum;
   }