Алгоритм последовательного поиска в неупорядоченном массиве
Имеется массив a[1 ... n], требуется найти элемент массива, равный P:
1. Установить i = 1.
2. Если a_i = P, алгоритм окончен удачно.
3. Увеличить i на 1.
4. Если i меньше или равно n, то перейти к шагу 2. В противном случае алгоритм
окончен неудачно.

Хотелось бы оценить сложность этого алгоритма. Наиболее естественно было бы оценивать сложность алгоритма по числу сравнений с искомым элементом. В худшем случае искомый элемент окажется на последнем месте или не будет найден вообще, тогда необходимо будет проделать n сравнений, то есть сложность алгоритма будет равна n. В среднем для поиска элемента в массиве требуется n/2 сравнений, поэтому затраты времени для больших массивов при последовательном поиске велики. Такой поиск также называют линейным, так как он решает задачу поиска с линейной сложностью по количеству сравнений.