[Solved] Data structure – run-time and Asymptotic bounds [closed]

To prove that f(n) = Θ(g(n)), you need to prove that there is a nonzero k such that

lim (n → ∞) f(n) / g(n) = k

In your case, we want to show that

lim (n → ∞) lg(n + a) / (lg n)

This is an indeterminate form of type ∞ / ∞, so we can apply l’Hôpital’s rule and take the derivative of the numerator and denominator to get

lim (n → ∞) lg(n + a) / (lg n) =

lim (n → ∞) (1 / n + a) / (1 / n) =

lim (n → ∞) n / (n + a)

This again is an indeterminate form, so applying l’Hôpital’s rule gives

lim (n → ∞) n / (n + a)

= lim (n → ∞) 1 / 1

= 1

Therefore, there is a nonzero constant (namely 1) such that the limit of lg(n + a) / lg n as n goes to infinity equals that constant, and therefore lg(n + a) = Θ(lg n).

Hope this helps!