Сложность бинарного поиска в структуре без произвольного доступа

Question

Выполнение двоичного поиска в отсортированном массиве имеет O(logN) сложность, где N - количество элементов в массиве.
Но если мы выполняем двоичный поиск в отсортированном (связанном) списке, то какова сложность?
Мы делаем logN сравнения среднего элемента диапазона, но чтобы добраться до диапазона, сложность составляет O(N) из-за того, что список не является структурой с произвольным доступом.
Такова сложность времени:
1) logN * O(N) = O(N) рассматривать logN как константу? или
2) logN*O(N) = O(NlogN) означает, что logN = O(logN) во всех случаях?

Что здесь правильно? 1 или 2?

Answer 1

Второе предположение верно, а первое неверно. Анализ Asymptoti c имеет дело с ростом. Если количество узлов увеличится, log (n) также увеличится. Вы не можете рассматривать его как константу. Для очень простого примера c, если у вас было 10 узлов, и для выполнения потребовалось 10 секунд, предположение, что 100 узлов требуют 200 секунд для выполнения, кажется более точным, чем предположение 100 секунд (без учета log (n)).