Что нужно сделать с массивом чтобы алгоритмическая сложность поиска элемента была линейной

Для линейного поиска (O(n)) не нужно ничего делать с массивом — он уже подходит. Просто перебираем элементы по одному до нахождения нужного.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Нюансы:

• Не требует сортировки или дополнительной памяти.
• Худший случай — весь массив (O(n)).
• Подходит для небольших или неотсортированных данных.

Для частых поисков лучше использовать другие структуры (хеш-таблицы, бинарный поиск в отсортированном массиве).