Em análise de algoritmos o desempenho relativo também depende do tamanho do problema. Um algoritmo de ordenação que é rápido para pequenas listas pode ser lento para longas listas. A solução habitual para este problema é expressar o tempo de execução (ou o número de operações) como uma função do tamanho de problema e funções de grupo em categorias que dependem de sua velocidade de crescimento quando o tamanho de problema aumenta.

No pior caso, a complexidade do algoritmo conhecido como Busca Linear é:

Alternativas:

a) O(n²)

b) O(1)

c) O(n)

d) O(log n)

e) O(n log n)