Oppgave 1

Permutasjoner med samme verdi først	Sum antall
5 står først	26
4 står først	26
3 står først	38
2 står først	46
1 står først	52

Gjennomsnittet:  (26 + 26 + 38 + 46 + 52)/120 = 188/120 = 2/3 + 2/4 + 2/5.

Her kommer alle de 120 permutasjonene av tallene 1 2 3 4 5 og for hver permutasjon er de tallene som er større enn det neste største foran markert med fet type:

     1 2 3 4 5    1 2 3 5 4    1 2 4 3 5    1 2 4 5 3
     1 2 5 3 4    1 2 5 4 3    1 3 2 4 5    1 3 2 5 4
     1 3 4 2 5    1 3 4 5 2    1 3 5 2 4    1 3 5 4 2
     1 4 2 3 5    1 4 2 5 3    1 4 3 2 5    1 4 3 5 2
     1 4 5 2 3    1 4 5 3 2    1 5 2 3 4    1 5 2 4 3
     1 5 3 2 4    1 5 3 4 2    1 5 4 2 3    1 5 4 3 2
     2 1 3 4 5    2 1 3 5 4    2 1 4 3 5    2 1 4 5 3
     2 1 5 3 4    2 1 5 4 3    2 3 1 4 5    2 3 1 5 4
     2 3 4 1 5    2 3 4 5 1    2 3 5 1 4    2 3 5 4 1
     2 4 1 3 5    2 4 1 5 3    2 4 3 1 5    2 4 3 5 1
     2 4 5 1 3    2 4 5 3 1    2 5 1 3 4    2 5 1 4 3
     2 5 3 1 4    2 5 3 4 1    2 5 4 1 3    2 5 4 3 1
     3 1 2 4 5    3 1 2 5 4    3 1 4 2 5    3 1 4 5 2
     3 1 5 2 4    3 1 5 4 2    3 2 1 4 5    3 2 1 5 4
     3 2 4 1 5    3 2 4 5 1    3 2 5 1 4    3 2 5 4 1
     3 4 1 2 5    3 4 1 5 2    3 4 2 1 5    3 4 2 5 1
     3 4 5 1 2    3 4 5 2 1    3 5 1 2 4    3 5 1 4 2
     3 5 2 1 4    3 5 2 4 1    3 5 4 1 2    3 5 4 2 1
     4 1 2 3 5    4 1 2 5 3    4 1 3 2 5    4 1 3 5 2
     4 1 5 2 3    4 1 5 3 2    4 2 1 3 5    4 2 1 5 3
     4 2 3 1 5    4 2 3 5 1    4 2 5 1 3    4 2 5 3 1
     4 3 1 2 5    4 3 1 5 2    4 3 2 1 5    4 3 2 5 1
     4 3 5 1 2    4 3 5 2 1    4 5 1 2 3    4 5 1 3 2
     4 5 2 1 3    4 5 2 3 1    4 5 3 1 2    4 5 3 2 1
     5 1 2 3 4    5 1 2 4 3    5 1 3 2 4    5 1 3 4 2
     5 1 4 2 3    5 1 4 3 2    5 2 1 3 4    5 2 1 4 3
     5 2 3 1 4    5 2 3 4 1    5 2 4 1 3    5 2 4 3 1
     5 3 1 2 4    5 3 1 4 2    5 3 2 1 4    5 3 2 4 1
     5 3 4 1 2    5 3 4 2 1    5 4 1 2 3    5 4 1 3 2
     5 4 2 1 3    5 4 2 3 1    5 4 3 1 2    5 4 3 2 1

Oppgave 2

  public static int antallNestMaks(int[] a)
  {
    if (a.length < 2)
      throw new IllegalArgumentException("Må ha a.length >= 2");

    int maksverdi = a[0], nestmaksverdi = a[1];
    if (maksverdi < nestmaksverdi)
    {
      maksverdi = a[1]; nestmaksverdi = a[0];
    }

    int antall = 0;

    for (int i = 2; i < a.length; i++)
    {
      if (a[i] > nestmaksverdi)
      {
        antall++;  // testen er sann

        if (a[i] > maksverdi)
        {
          nestmaksverdi = maksverdi;  // ny nest størst
          maksverdi = a[i];           // ny størst
        }
        else
        {
          nestmaksverdi = a[i];  // ny nest størst
        }
      }
    }

    return antall;

  } // antallNestMaks

Oppgave 3

Det beste tilfellet får vi hvis de to største ligger først. Da trengs én sammenligning for å avgjøre hvem av dem som er størst. Deretter vil sammenligningen a[i] > nestmaksverdi bli utført n - 2 ganger og er usann hver gang. Tilsammen n - 1 sammenligninger.