В п. . сложностью названо количество элементарных шагов вычислительного процесса, порождённого алгоритмом. Считать надо действия при выполнении на заданных входных данных, а не только строки или команды в его записи. Например, команда «прибавь очередное число» в цикле может быть записана один раз, но для списка из чисел она выполнится раз.
Наибольшее влияние на число шагов обычно оказывает объём входных данных. Если алгоритм просматривает список длины и сравнивает каждый элемент с искомым, ему может понадобиться до сравнений. При увеличении длины списка в два раза возможное число таких сравнений тоже возрастает в два раза. Поэтому сложность выражают как функцию от размера входа, например для такого просмотра.
Итак, сложность характеризует объём работы исполнителя на данных заданного размера.
