Algoritmos e Estrutura de Dados · FCM · 2022 | Questão sqc-gp036815

Análise de Complexidade Assintótica

Gabarito: letra C. O tempo de execução para uma entrada de tamanho 40 será de 1,7 minutos, pois a função tem comportamento $O(n^5)$ . Para $n=10$ , o tempo é $0.1s$ , então a constante $c$ é $0.1 / (10^5) = 10^{-6}s$ . Para $n=40$ , o tempo é $c \cdot 40^5 = 10^{-6} \cdot 102.400.000 = 102,4$ segundos, que equivalem a $102,4 / 60 \approx 1,7067$ minutos, ou seja, 1,7 minutos.

A questão testa o entendimento de que, em complexidade assintótica, o tempo de execução escala proporcionalmente à função de crescimento (no caso, $n^5$ ), e não linearmente. O erro comum é multiplicar o tempo base pelo fator de aumento do tamanho da entrada (4 vezes), o que daria $0,4s$ , ou considerando um expoente errado.

Alternativa A — ❌ Incorreta

3,2 segundos. Esse valor seria obtido se a complexidade fosse $O(n^4)$ para um fator de escala $4^4 = 256$ , multiplicando $0,1 \times 256 = 25,6s$ , ou ainda um cálculo incorreto de $40^5$ (como $40^5 = 1.024.000$ ?) levando a $1.024.000 \times 10^{-6} = 1,024s$ ??? Não corresponde a nenhum raciocínio direto. Possível erro: considerar $40^5 = (4 \times 10)^5 = 4^5 \times 10^5 = 1024 \times 100000 = 102.400.000$ , depois dividir por $10^6$ (ao invés de $10^7$ ) dando $10,24s$ ou algo assim. A alternativa está claramente errada.

Alternativa B — ❌ Incorreta

24,3 segundos. Provém de um equívoco na potência: talvez $0,1 \times 4^3 = 0,1 \times 64 = 6,4s$ ou $0,1 \times 4^4 = 25,6s$ (próximo a 24,3?). Ou então $0,1 \times 243 = 24,3s$ , onde 243 seria $3^5$ ? Não procede. A banca insere esse distrator para confundir quem calcula $40^5$ errado ou usa $4^5 = 1024$ multiplicando por $0,1$ sem a devida base decimal.

Alternativa C — ✅ Correta ⟵ GABARITO

1,7 minutos. Conforme o cálculo: $10^{-6} \times 40^5 = 102,4s = 1,7067min \approx 1,7min$ . Exato.

Alternativa D — ❌ Incorreta

5,2 minutos. Corresponde a aproximadamente $0,1 \times 40^4 = 0,1 \times 2.560.000 = 256.000s$ ? Não. Na verdade, $5,2min = 312s$ . Se $c \cdot 40^5 = 102,4s$ , para chegar a 312s o expoente seria maior que 5, ou a constante maior. Possível: confundir $n^5$ com $n^6$ resultaria em $10^{-6} \cdot 40^6 = 4096s \approx 68min$ , longe. Então é um distrator aleatório.

Alternativa E — ❌ Incorreta

13 minutos. $13min = 780s$ . Também não corresponde a nenhum expoente simples. Se fosse $O(n^4)$ , $40^4 = 2.560.000$ , $c \cdot 2.560.000 = 2,56s$ ; se $O(n^6)$ , $40^6 = 4.096.000.000$ , $c \cdot 4.096.000.000 = 4096s = 68,27min$ . Então 13min está entre esses, sem justificativa.

NÃO CAIA NESSA!

A principal armadilha é achar que o tempo cresce linearmente com o tamanho da entrada (ex.: $0,1 \times 4 = 0,4s$ ) ou que o expoente 5 se aplica apenas ao fator 4 ( $4^5 = 1024$ , resultando em $102,4s$ — esse valor é correto, mas muitos esquecem de converter para minutos ou confundem a notação de potência). Lembre-se: em $O(n^k)$ , o tempo escala com $fator^k$ , e a constante é determinada por um ponto conhecido. A conversão para minutos é o passo final.

\text{Tempo para } n = 40 = \frac{0,1}{10^5} \times 40^5 = 10^{-6} \times 102.400.000 = 102,4 \text{ segundos} = 1,7067 \text{ minutos} \approx 1,7 \text{ min}