A alegação dePágina da Wikipedia para pilhas binárias é que a inserção é O (logn) no pior caso, mas O (1) em média:

O número de operações necessárias depende apenas do número de níveis em que o novo elemento deve subir para satisfazer a propriedade da pilha, portanto, a operação de inserção tem uma complexidade de tempo no pior caso de O (logn), mas com uma complexidade média de O (1).

opágina vinculada tenta justificar isso da seguinte maneira:

No entanto, em média, o elemento recém-inserido não viaja muito longe na árvore. Em particular, assumindo uma distribuição uniforme de chaves, ele tem uma chance e meia de ser maior que seu pai; tem uma chance e meia de ser maior que seu avô, uma vez que é maior que seu pai; ele tem uma chance e meia de ser maior que seu bisavô, uma vez que é maior que seu pai, e assim por diante [...] de modo que, no caso médio, a inserção leva tempo constante

Certamente isso é um absurdo? Parece-me que se a árvore fosse ordenada aleatoriamente, haveria uma chance de 50/50 de um novo elemento ser maior que seu pai; mas, já que, grosso modo, os elementos grandes afundam no fundo, as chances são muito menores que 50/50 à medida que a pilha cresce.

Isso está certo?

Tem sido assim na Wikipedia há vários meses ...