Каким образом реализовать поиск элемента по ключу с временной сложностью O(n)?

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

В C# это можно реализовать, например, перебором элементов массива или списка:

int FindIndexByKey(List<KeyValuePair<int, string>> list, int key) {
    for (int i = 0; i < list.Count; i++) {
        if (list[i].Key == key) {
            return i; // найден индекс
        }
    }
    return -1; // не найден
}

Здесь поиск идет по всем элементам списка, что соответствует O(n). Такой подход используется, если нет индексированных структур данных (например, словаря), или когда данные не отсортированы.