Знаю. Но ты не учитываешь, что i может достигать размера n, и поэтому должен ползти в формулу.
Получить указатель на i-й элемент листа это O(i). Если лист размера n/2 и отсчитывать от середины, то O(n/2 - i). При i в худшем случае это будет O(n/4), а это все равно O(n). Короче похуй на самом деле