Qual a complexidade de T 1(n)=(7^* n) lg dotn+lg n ; T 2(n)=2^n+n^2+30; e T3(n, k) =k+n, onde k<=n? Da menor, para a maior, determine a ordem das complexidades.

Passo 1

Beleza! Vamos resolver esse exercício juntos. O enunciado pede para determinar a complexidade de três funções diferentes e depois ordenar essas complexidades da menor para a maior. Estamos lidando com análise de complexidade de algoritmos, que usa notações como Big-O para descrever como o tempo de execução cresce com o tamanho da entrada $ n $. Vamos precisar entender conceitos como exponenciais, logaritmos e polinômios para resolver isso.

Passo 2

Vamos começar entendendo cada uma das funções:
  1. T₁(n) = 7ⁿ * log n + log n
    • Aqui temos um termo exponencial $ 7^n $ multiplicado por um logaritmo de $ n $, e depois somamos outro logaritmo de $ n $.
  2. T₂(n) = 2ⁿ + n² + 30
    • Nesta função, temos uma parte exponencial $ 2^n $, uma parte polinomial $ n^2 $, e uma constante 30.
  3. T₃(n, k) = k + n, onde $ k \leq n $
    • Aqui, temos uma soma linear de $ k $ e $ n $, com a condição de que $ k $ não é maior que $ n $.

Passo 3

Vamos analisar a complexidade de cada função separadamente.
Para T₁(n) = 7ⁿ * log n + log n:
  • O termo dominante aqui é $ 7^n * log n $, porque exponenciais crescem muito mais rápido que logaritmos.
  • Portanto, a complexidade de T₁(n) é da ordem de $ O(7^n * log n) $.
Para T₂(n) = 2ⁿ + n² + 30:
  • O termo dominante é $ 2^n $, já que exponenciais superam polinômios e constantes.
  • Assim, a complexidade de T₂(n) é $ O(2^n) $.
Para T₃(n, k) = k + n, onde k ≤ n:
  • Como $ k $ é no máximo $ n $, podemos considerar $ k $ como $ O(n) $.
  • A soma $ k + n $ então é $ O(n) + O(n) = O(n) $.
  • Portanto, a complexidade de T₃(n, k) é $ O(n) $.

Passo 4

Agora que temos as complexidades:
  • T₃(n, k): $ O(n) $
  • T₂(n): $ O(2^n) $
  • T₁(n): $ O(7^n * log n) $
Precisamos ordenar da menor para a maior complexidade. Sabemos que:
  • $ O(n) $ cresce mais lentamente que qualquer exponencial.
  • Entre as exponenciais, $ 2^n $ cresce mais devagar que $ 7^n $, mesmo multiplicado por um logaritmo.

Resposta

Da menor para a maior complexidade, a ordem é:
  1. T₃(n, k): $ O(n) $
  2. T₂(n): $ O(2^n) $
  3. T₁(n): $ O(7^n \cdot \log n) $

Exercícios relacionados