PUERTA | PUERTA CS 1999 | Pregunta 46

Si T1 = O(1), dé la coincidencia correcta para los siguientes pares:

(M) Tn=Tn−1+n           (U) Tn=O(n)
(N) Tn=Tn/2 +n          (V) Tn=O(nlogn)
(O) Tn=Tn/2 +nlogn      (W) T=O(n^2)
(P) Tn=Tn−1 +logn       (X) Tn=O(log^2n) 

(A) MW NV OU PX
(B) MW NU OX PV
(C) MV NW OX PU
(D) MW NU OV PX

Respuesta:
Explicación:

(M) T(n) = T(n-1) + n = 1 + 2 + 3 + … + n = O(n^2) — choice is (W)

(N) T(n) = T(n/2) + n = O(n), using master theorem case -3, - choice is (U)

(O) T(n) = T(n/2) + nlogn = O(nlogn), using master theorem case -3, - choice is (v)

(P) T(n) = T(n-1) + logn = log 1 + log 2 + log 3 + … + log n 
         = log(1*2*3…*n) = log(n!) = nlogn = O(nlogn) - choice is (v) 

Por lo tanto, ninguna opción coincide.

Cuestionario de esta pregunta