Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

Acessar um elemento de um array pelo índice leva:

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

Qual notação descreve um limite inferior de crescimento?

1. AO (O grande)
2. BΩ (Ômega grande)
3. Co (o pequeno)
4. DΘ (Theta grande)

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(mn log n)
2. BO(m + n)
3. CO(mn)
4. DO(2^m+n)

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(n) e espaço O(1)
2. BTempo O(log n) e espaço O(n)
3. CTempo O(2ⁿ) e espaço O(1)
4. DTempo O(n) e espaço O(n)

2²ⁿ está em O(2ⁿ)?

1. ANão, porque 2²ⁿ cresce mais devagar que 2ⁿ
2. BSim, porque fatores constantes no expoente são sempre ignorados no O grande
3. CNão, porque 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
4. DSim, porque ambos são exponenciais