Uma busca linear na maioria dos casos vai ser O(N), pois você precisa percorrer todos os elementos de uma lista, vetor e etc. Nesse caso do documento você vai utilizar um for encadeado mas vai fazer uma busca linear no documento, pois vai "varrer" ele uma só vez, considerando que ele tenha N palavras, você vai fazer N operações para realizar a busca no pior caso, portanto o for encadeado não é responsável por deixar a quantidade de operações quadrática em relação ao tamanho da entrada nesse caso.
Com relação a otimização da busca, ela pode ser feita quando sua lista de elementos é ordenada, podendo assim utilizar a busca binária.