Функция, которая имеет время работы O(n); то есть если функция работает на коллекции из n элементов, функция возможно изучить каждый элемент в коллекции, выполняя до n сравнений.