GabaritoA — O (lg n)
Gabarito: letra A. A profundidade média de um nó em uma árvore binária de busca (BST) construída aleatoriamente com n nós é O(log n). Esse é um resultado clássico da análise probabilística de BSTs: a altura esperada é Θ(log n), e a profundidade média de um nó também é Θ(log n). Portanto, a alternativa A está correta.
Expressa corretamente a complexidade: O(log n). A profundidade média de um nó em uma BST aleatória é proporcional ao logaritmo do número de nós. Isso decorre do fato de que, em média, a árvore é aproximadamente balanceada.
O(n log n) é a complexidade típica de algoritmos de ordenação como mergesort ou heapsort, não da profundidade média de um nó em uma BST. A profundidade média é O(log n), não O(n log n). A confusão pode surgir com o custo total de construção da árvore, que é O(n log n), mas a profundidade de um nó individual é logarítmica.
"1 + (n lg n)" não é uma notação assintótica correta para profundidade média. Além disso, a profundidade média não é linear em n, mas logarítmica. O termo "1 +" é irrelevante; a notação correta seria O(log n), não n log n.
"1 + O(log n)" está próximo, mas o "1 +" é desnecessário e não reflete a notação padrão. O resultado correto é apenas O(log n), pois constantes aditivas são absorvidas pela notação O. Além disso, a profundidade média não é exatamente 1 + algo; ela é aproximadamente 2 ln n, que é O(log n) sem constante aditiva.
"1 + O(lg n/(1+n))" é uma expressão confusa. Para n grande, lg n/(1+n) tende a 0, então isso seria O(1), o que está errado. A profundidade média cresce com n, não tende a constante.
Conclusão: A única alternativa que expressa corretamente a complexidade assintótica da profundidade média de um nó em uma BST aleatória é a letra A — O(log n).
Link permanente: /questoes/qg045234