Questões de Complexidade de Algoritmos (Algoritmos e Estrutura de Dados)

O analista Raimundo sabe que a indução de árvores de decisão é uma das formas mais simples, e ainda assim mais bem sucedidas, de aprendizagem de máquina. No entanto, ao aplicá-la em alguns problemas da empresa em que atua, o algoritmo de aprendizagem-em-árvore-de-decisão gera uma grande árvore quando realmente não há padrão a ser encontrado nos dados.
O nome do problema encontrado por Raimundo é

Na análise de complexidade de algoritmo, uma função f(n) é Ω (t(n)) se, e somente se, a seguintecondição for satisfeita, onde c e k são constantes positivas:

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:

Os algoritmos são sequências lógicas e finitas de passos que resolvem problemas específicos, sendo a base para o desenvolvimento de sistemas computacionais. Sobre algoritmos, analise as afirmativas a seguir:
I. Algoritmos recursivos são aqueles que se definem em termos de si mesmos, exigindo uma condição base para evitar chamadas infinitas.
II. A complexidade de tempo de um algoritmo refere-se exclusivamente ao número de passos necessários para executar o código, desconsiderando a entrada do problema.
III. Um algoritmo pode ser implementado em diferentes linguagens de programação, desde que sua lógica seja preservada.
Está correto o que se afirma em:

O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2^N + log₂(N) operações para ser executado. Já o Cbusca requer N⁴ + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.

José deve escolher o algoritmo: