Question

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

Answer 1

Tomando como base as noções básicas de logaritmo, podemos afirmar que a resposta para o menor valor de n em questão é 15.

Como encontrar o valor de n?

Para entradas de tamanho n, devemos ter em mente que o tempo de execução do algoritmo A é 100n2 e de B é 2n. Para que A funcione mais rápido que B, 100n2 deve ser menor que 2n. A (complexidade de tempo quadrática) funcionará muito mais rápido que B (complexidade de tempo exponencial) para valores muito grandes de n. Sendo assim, devemos começar a verificar a partir de n=1 e subir para valores de n que são potência de 2. Em algum lugar entre 8 e 16, A começa a funcionar mais rápido que B. Continuaremos verificando o valor de n, mas agora usando uma busca binária até encontrarmos n=15, em que A começa a correr mais rápido do que B.

Aprenda mais sobre a ciência da computaçao em: https://brainly.com.br/tarefa/10242344

#SPJ4

Answer 2

O menor valor de "n" é 15 de acordo com as noções básicas de logarítmo.

Encontrando o Valor de "n"

Primeiro devemos verificar os tempos de execução disponíveis antes de colocá-las na fórmula:

• Algoritmo A - Tempo de execução = 100n2
• Algoritmo B - Tempo de execução = 2n

Após verificarmos os tempos de execução de cada algorítmo resolvemos da seguinte forma:

100$n^{2}$ $\leq 2^{n}$

lg(100$n^{2}$) $\leq$ n

lg(100) + 2lgn $\leq$ n

6.65 + 2lgn $\leq$ n

n $\leq$ 14.325

Como "n" é $\geq$ ou = 15, o algoritmo é melhor que o exponencial.

Para saber mais sobre Algoritmos, acesse: https://brainly.com.br/tarefa/42727963

#SPJ4