nale V para a(s) verdadeira(s) e F para a(s) falsa. I. ( ) O limite assintótico superior de T(n) é O(2n). II. ( ) Se T(n) ≤ c2n - 4n, então T(n) ...

nale V para a(s) verdadeira(s) e F para a(s) falsa. I. ( ) O limite assintótico superior de T(n) é O(2n).

II. ( ) Se T(n) ≤ c2n - 4n, então T(n) ≤ c(2n - 1 + 2n/2) - 4n, para n ≥ 0 e c > 0.

III. ( ) O limite assintótico inferior de T(n) é Ω(n2)

IV. ( ) Se T(n) ≥ cn2 e c ≤ ½, então T(n) ≤ cn2 + (1 - 2c)n + c.

Agora, assinale a alternativa que apresenta a sequência correta:

V, F, V, F

Resposta correta. Supondo que T(n) = c2n – 4n para c > 0, temos pelo método da substituição:

T(n) = c2n-1 – 4(n – 1) + c2n/2 - 4n/2 + n

= c(2n – 1 + 2n/2) – 5n + 4 (para n = 1/4)

= c(2n – 1 + 2n/2) – 4n (para n = 2)

= c(2n – 1 + 2n - 1) – 4n = c2n – 4n

= O(2n)

Agora, supondo T(n) = cn2 pelo método da substituição, temos:

T(n) = c(n – 1)2 + c(n/2)2 + n

= cn2 – 2cn + c + cn2/4 + n

= (5/4)cn2 + (1 – 2c)n + c

= cn2 + (1 – 2c)n + c (para c = ½)

= cn2

= O(n2)

[object Object]
[object Object]
[object Object]
[object Object]
a) V, V, F, F
b) F, V, V, F
c) V, F, V, F
d) F, F, V, V