Considere o algoritmo de ordenação para um vetor de inteiros em linguagem Javascript descrito a seguir:
sort = (array) => {
if (array.length <= 1) {
return array;
}
const pivot = array[array.length - 1];
const left = [];
const right = [];
for (let i = 0; i < array.length - 1; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return [...sort(left), pivot, ...sort(right)];
}
Considerando n como o tamanho do vetor, assinale a alternativa CORRETA que corresponde à complexidade média de tempo do algoritmo na notação Big-O: