Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina?

Question

Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona mais rápido que um algoritmo cujo tempo de execução é 2n na ...

Ed · Answer

Para encontrar o menor valor de $ n $ tal que $ 100n^2  2
  \]

- Para \( n = 2 $:
  $$
  100(2^2) = 400 \quad \text{e} \quad 2^2 = 4 \quad \Rightarrow \quad 400 > 4
  $$

- Para $ n = 3 $:
  $$
  100(3^2) = 900 \quad \text{e} \quad 2^3 = 8 \quad \Rightarrow \quad 900 > 8
  $$

- Para $ n = 4 $:
  $$
  100(4^2) = 1600 \quad \text{e} \quad 2^4 = 16 \quad \Rightarrow \quad 1600 > 16
  $$

- Para $ n = 5 $:
  $$
  100(5^2) = 2500 \quad \text{e} \quad 2^5 = 32 \quad \Rightarrow \quad 2500 > 32
  $$

- Para $ n = 6 $:
  $$
  100(6^2) = 3600 \quad \text{e} \quad 2^6 = 64 \quad \Rightarrow \quad 3600 > 64
  $$

- Para $ n = 7 $:
  $$
  100(7^2) = 4900 \quad \text{e} \quad 2^7 = 128 \quad \Rightarrow \quad 4900 > 128
  $$

- Para $ n = 8 $:
  $$
  100(8^2) = 6400 \quad \text{e} \quad 2^8 = 256 \quad \Rightarrow \quad 6400 > 256
  $$

- Para $ n = 9 $:
  $$
  100(9^2) = 8100 \quad \text{e} \quad 2^9 = 512 \quad \Rightarrow \quad 8100 > 512
  $$

- Para $ n = 10 $:
  $$
  100(10^2) = 10000 \quad \text{e} \quad 2^{10} = 1024 \quad \Rightarrow \quad 10000 > 1024
  $$

- Para $ n = 11 $:
  $$
  100(11^2) = 12100 \quad \text{e} \quad 2^{11} = 2048 \quad \Rightarrow \quad 12100 > 2048
  $$

- Para $ n = 12 $:
  $$
  100(12^2) = 14400 \quad \text{e} \quad 2^{12} = 4096 \quad \Rightarrow \quad 14400 > 4096
  $$

- Para $ n = 13 $:
  $$
  100(13^2) = 16900 \quad \text{e} \quad 2^{13} = 8192 \quad \Rightarrow \quad 16900 > 8192
  $$

- Para $ n = 14 $:
  $$
  100(14^2) = 19600 \quad \text{e} \quad 2^{14} = 16384 \quad \Rightarrow \quad 19600 > 16384
  $$

- Para $ n = 15 $:
  \[
  100(15^2) = 22500 \quad \text{e} \quad 2^{15} = 32768 \quad \Rightarrow \quad 22500

Ed · Answer

Para encontrar o menor valor de $ n $ em que o algoritmo com tempo de execução de $ 100n^2 $ é mais rápido que o algoritmo com tempo de execução de $ 2n $, podemos igualar as duas expressões e resolver a equação.

$ 100n^2 = 2n $

$ 100n^2 - 2n = 0 $

$ 2n(50n - 1) = 0 $

Isso nos dá duas soluções: $ n = 0 $ e $ n = \frac{1}{50} $. Portanto, o menor valor de $ n $ para o qual o algoritmo com tempo de execução de $ 100n^2 $ é mais rápido que o algoritmo com tempo de execução de $ 2n $ é $ n = \frac{1}{50} $.

Estrutura de Dados

Exercícios Estrutura de Dados

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Exercícios Estrutura de Dados

Mais conteúdos dessa disciplina