Considerando a recorrência T(n) = T(n – 1) + T(n/2) + n, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s...

Considerando a recorrência T(n) = T(n – 1) + T(n/2) + n, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).

I. ( ) O limite assintótico superior de T(n) é O(2 ).
II. ( ) Se T(n) ≤ c2 – 4n, então T(n) ≤ c(2 + 2 ) – 4n, para n ≥ 0 e c > 0.
III. ( ) O limite assintótico inferior de T(n) é Ω(n )
IV. ( ) Se T(n) ≥ cn e c ≤ ½, então T(n) ≤ cn + (1 – 2c)n + c.

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

I. ( ) O limite assintótico superior de T(n) é O(2 ).
II. ( ) Se T(n) ≤ c2 – 4n, então T(n) ≤ c(2 + 2 ) – 4n, para n ≥ 0 e c > 0.
III. ( ) O limite assintótico inferior de T(n) é Ω(n )
IV. ( ) Se T(n) ≥ cn e c ≤ ½, então T(n) ≤ cn + (1 – 2c)n + c.
a. V, F, V, F.
b. F, V, F, V.
c. V, V, F, F.
d. V, V, F, V.
e. F, F, V, V.