Página 1 de 1

operações com a notação O

MensagemEnviado: Qua Dez 12, 2018 00:59
por bebelo35
1) Realize as seguintes operações:

a) Suponha três trechos de programa cujos tempos são: O(log n),O(n²) e O(n logn)

b) O(n²+4)*O(n²-4)

c) (n³+6)*O(n³-6)

Re: operações com a notação O

MensagemEnviado: Ter Jan 22, 2019 11:56
por adauto martins
a)
usando a definiçao de desiqualdades,teremos:
a)
0(log n) \leq \left|log n \right|\leq \left|n.log n \right|\leq O(n.logn),p/n\succ 1,n \rightarrow \infty...
O(n.logn)\leq \left|n.logn \right|\leq \left|n \right|.\left|logn\leq \left| \right| n\right|.\left|n \right|\leqO(n.logn)\leq \left|n.logn \right|\leq \left|n \right|.\left|logn\leq \left| \right| n\right|.\left|n \right|\leq \leq \left|{n}^{2} \right|\leq O({n}^{2})...,logo:
O(n.logn)\prec O(logn) \prec O({n}^{2})...
b)
O({n}^{2}+4).O({n}^{2}-4)=O({n}^{2}).O({n}^{2})=O({n}^{(2+2)})=O({n}^{4})......exercicio,use a definiçao e mostre essa propriedade...
c)similar a res. b)...