Remoção com O(log(N))?

"Se você precisar procurar pelo elemento primeiro, então o tempo será linear, afinal passará por todas as células no pior caso."

Eu acho que aproveitando o poder da lista duplamente encadeada podemos otimizar o algoritmo de remoção, vocês me ajudam a validar a idéia? Talvez eu estou errando na nomenclatura, não sei se O(log(N)) (logaritmo de N) seria o correto de dizer, mas em simples palavras eu acho que ao menos a metade do N da pra economizar.

Vejam minha linha de raciocínio:

        if(posicaoParaRemover <= tamanho/2) {
            //busca do inicio até a posicao, pois o objeto esta mais perto do head
        } else {
            //busca do fim até a posição, pois o objeto esta mais perto do tail
        }

Mesmo dividindo pela metade ainda é linear?

Obrigado!