Pensando por exemplo numa simples leitura de documento em que precisamos buscar uma palavra em específico.

A primeira iteração seria sobre todas as linhas, a segunda iteração seria sobre todas as palavras desta linha buscando a específica. Qual seria a alternativa, senão "for" encadeado? 

Aliás, sei que há também aquelas a lógica vetorial para tornar estas buscas mais rápidas, como se fossem "índices" de um livro que lendo ele você já sabe aonde está cada coisa do livro propriamente dito, mas não se aplica.

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.

Pensando por exemplo numa simples leitura de documento em que precisamos buscar uma palavra em específico. A primeira iteração seria sobre todas as linhas, a segunda iteração seria sobre...