Un algorithme est de complexité linéaire si le temps de calcul croît
de façon linéaire en fonction du nombre de données. Si vous traitez
deux fois plus de données, le temps d'exécution sera multiplié par
deux. Par exemple, la recherche séquentielle dans un tableau non trié
est de complexité linéaire. En effet, on effectue une recherche en
parcourant le tableau avec une boucle (ou un algorithme
récursif). Chacune des itérations se fait en temps constant, il suffit
donc de compter le nombre d'itérations. Dans le pire des cas,
l'élément que l'on recherche est celui qui est examiné en dernier. Il
est donc nécessaire d'effectuer 
itérations.