Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

1. AO(n)
2. BO(n²)
3. CO(n log n)
4. DO(1)

O que significa f(n) = Θ(g(n))?

1. Af cresce no mesmo ritmo que g, limitada por cima e por baixo por múltiplos constantes de g
2. Bf cresce estritamente mais devagar que g
3. Cf é sempre menor que g para todo n, então g a limita por cima, mas nunca por baixo
4. Df cresce estritamente mais rápido que g

O que é recursão?

1. AUm laço que nunca termina
2. BUm tipo de estrutura de dados
3. CUma função que chama a si mesma com entradas menores
4. DUm método de ordenação

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:

1. ALogarítmica
2. BExponencial
3. CLinear
4. DConstante

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AA base só importa para n pequeno
2. BTodos os logaritmos em computação têm base 10, então ela fica implícita
3. CLogaritmos de bases diferentes diferem apenas por um fator constante
4. DOs logaritmos são sempre arredondados para inteiros

Por que a busca binária não dá tempo O(log n) numa lista simplesmente encadeada?

1. AAs comparações entre nós de lista encadeada são mais lentas
2. BListas encadeadas não podem ser ordenadas
3. CA busca binária precisa de pelo menos o dobro da memória
4. DChegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice

A multiplicação de Karatsuba satisfaz T(n) = 3T(n/2) + O(n). Qual é a solução?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), cerca de n^1,585