APS1 - Complexidade (1)

Prévia do material em texto

1 
APS 1 
Professor: Sérgio Assunção Monteiro 
e-mail: smonteiro@unicarioca.edu.br 
1. A atividade deve ser entregue individualmente no local apropriado do AVA 
2. As resoluções da atividade devem ser digitadas, ou escritas em letra legível 
3. A atividade deve conter: 
• Nome da disciplina 
• Código da Turma 
• Nome e matrícula do aluno 
4. A data de entrega é até 30/09/2021. 
5. Esta atividade vale 4,0 pontos na composição da nota da AV1. 
6. Todas as respostas devem ser justificadas. 
7. O arquivo deve estar no formato PDF 
Questão 1 - (2,0 Pontos) 
 
Dada a expressão 5𝑛3 + 2𝑛 + 993 = 𝜃(𝑛3). Verifique sua validade através do método de 
indução matemática. Caso seja válida, apresente explicitamente as constantes 𝑛0, 𝑐1𝑒 𝑐2. 
 
Questão 2 - (2,0 Pontos) 
 
Observe o trecho de programa abaixo: 
 
int x = 0, y = 0; 
for (i = 0; i < N; i++) { 
 x + = 100; 
} 
for (j = 0; j < M; j++) { 
 y -= 100; 
} 
 
Obtenha as complexidades de tempo e espaço do programa usando a notação 𝑂(. ).