Olá,
poderia explicar por que o consumo de tempo para construir a tabela com tratamento de colisões por encadeamento é quadrático?
Oi Raphael
por que o consumo de tempo para construir a tabela com tratamento de colisões por encadeamento é quadrático?
Legal você ter perguntado!
Temos apenas duas lista.
O número de chaves em alguma delas é pelo menos n/2.
Antes de inserirmos uma chave precisamos verificar se ela está na lista.
O consumo de tempo dessa verificação para a maior lista é ≥ 1 + 2 + ... + n/2 ~ n2 (custo de n/2 buscas malsucedidas).