Oi Maurilio, tudo bem?
Peço desculpas pela demora em obter retorno, principalmente porque se tratava de algo urgente.
Vou exemplificar com a lista ligada. Operações de adicionar, remover e buscar um elemento específico têm custo O(n), isso porque precisamos, no pior caso, percorrer os n elementos da lista para encontrar esse elemento e realizar a operação. Agora, para retornar o primeiro elemento de uma lista, só pegamos o atributo elemento da lista encadeada e realizamos a operação, sem precisar percorrê-la. Por isso, ela tem custo O(1). Fazendo uma definição bem simples, toda vez que precisamos percorrer toda uma estrutura, o custo deixa de ser constante e passa a ser do tamanho da estrutura.
Em listas duplamente ligadas, esse custo ainda é o mesmo.
Com relação à árvore, esse custo de percorrer a estrutura até encontrar um nó específico passa a ser O(log n) - se a árvore está balanceada - , por ela se dividir em várias e não precisarmos passar por todos os nós.
Espero ter ajudado, abraços!
Caso este post tenha lhe ajudado, por favor, marcar como solucionado ✓. Bons Estudos!
