function_1(tableau1, tableau2) :
- Complexité algorithmique : O(n * m)
  - Dans le pire cas, où n est la taille du tableau 1 et m la taille du tableau 2.
function_2(x) :
- Complexité algorithmique : O(x)
  - La boucle while fait x itérations, et x est décrémentée de 1 jusqu'à 0.
function_3(x) :
- Complexité algorithmique : O(1)
  - En fonction de la valeur de x, une des trois conditions exécute une opération simple.

EXO3

Pour cette fonction, on a :

La première boucle for : O(g)
Malloc : O(1)
Deuxième boucle for : O(g * n)
Bubblesort : O(g * n²)
Free : O(1)
find_rank_student : O(g * n²) pour Bubblesort + O(g * n) : O(g * n^3)

Simplification :

On peut enlever les O(1) et conserver la complexité la plus élevée, donc O(g * n^3).

Complexité algorithmique pour sort_student : O(g * n^3)

EXO4

Voici le code :

def tri(t):
    for tab in t:
        for i in range(len(tab)):
            for j in range(len(tab) - 1):
                if tab[j] > tab[j + 1]:
                    tab[j], tab[j + 1] = tab[j + 1], tab[j]
    
    for i in range(len(t)):
        for j in range(len(t) - 1):
            if t[j][0] > t[j + 1][0]:
                t[j], t[j + 1] = t[j + 1], t[j]
    
    print(t)

tri([[3, 9, 6], [9, 3, 8], [10, 67, 55]])

Complexité algorithmique de ma fonction tri() :

Pour m éléments, la complexité algorithmique de chaque sous-liste est O(m²), multipliée par le nombre de sous-listes, cela fait : O(n * m²).
Pour le tri final, la complexité algorithmique est O(n²).

On garde la plus élevée, donc pour ma fonction : O(n * m²) + O(n²).