Podemos dizer que a função é da ordem de:

A resposta correta é: “Θ(n)” Justificativa: Utilizando o teorema mestre, temos: a = 1, b = 10/9 e f(n) = n. Além disso, n^(log_(b)a) = n^(log_(10 / 9)1) = n⁰ = 1. Como f(n) = Θ(n^(log_(b)a + x)) para x > 0, podemos verificar se o caso 3 do teorema mestre é aplicável. Para isso, vemos se af(n/b) <= cf(n) para algum c < 1 e para n grande. Assim, temos que: 9n/10 <= c*n para c = 9/10. Dessa forma, T(n) = Θ(n).