# Correction Examen blanc (TD5)

## Question 1: Déroulages

[Les déroulages sont ici](https://docs.google.com/spreadsheets/d/1R3zuzhH6QuhK3x8xLb7GDz84JvBeo2S4_P39Qa5eZBs/edit?usp=sharing)

## Question 2: Calcul de $f(N)$ pour ```g```

Le pire cas est tout le temps puisque la fonction est obligée de parcourir tout le tableau "t2". Déroulons l'algorithme pour 2 cas de N = 2 et N = 3.

A partir des déroulages concrets on produit les déroulages abstraits.

Dans les déroulages abstraits, pour N = 2 on obtient 9 losanges et pour N = 3 on obtient 11 losanges. on peut en déduire que f(N) = 1 + N+1 + N+3. On en déduit $f(N)= 2N+5$.

## Question 3: Classe de complexité de ```g```

Donc la complexité de la fonction est en $O(f(N)) = O(2N +5) = O(N)$.

## Question 4: Définir une fonction ```h``` plus efficace que ```g```

Version 1.

  public static int [] h1(int [] t, int k) {
	  int[] tab= new int[t.length+1];
	  boolean inser= false;
	  int j=0;
	  for(int i=0; i<t.length; i++) {
		  if(k>t[i]) {
			  tab[j]=t[i];
		  }else if(!inser)  {
			  tab[j]=k;
			  inser=true;
		  }else
			  tab[j]=t[i];
		  j++;
	  }
	  return tab;
  }

## Question 5: Pire cas pour ```h```

## Question 6: Déroulages de ```h```

## Question 7: Calcul de $f(N)$ pour ```h```

Sur ```h1``` il y a des chances que ça soit $f(N)= N+2$. A vous de vérifier!

## Question 8: Classe de complexité de ```h```

$O(f(N))= O(N+2) = O(N)$

## Question 9: Que peut-on en déduire sur ```h```?