Asymptotic bound $T(n)=T(n/3+\lg n)+1$

Question

How would I go about finding the upper and lower bounds of $T(n)=T(n/3+\lg(n))+1$?

Answer 1

Not sure how tight a bound you need, but here is an idea.

Compare your recurrence to the one that satisfies $X_n = X_{n/3} + 1$ (without the log) - what is the relationship between $T_n$ and $X_n$? Note that when you solve, $X_n = \Theta(\log n)$.

Next item is in the other direction. Compare $T_n$ to $Y_n = Y_{n-1}+1$, and note that $Y_n = \Theta(n)$.

If you fill in the blanks, you get an inequality bounding on both sides.

Answer 2

As answered already, the lower bound is $\Theta(\lg n)$.

If you want a tighter upper bound, you can observe that for any $n>32$, $\lg(n) < n/6$. So if you replace $T(n/3+\lg n) + 1$ with $T(n/2)+1$, this behaves like $\Theta(\lg(n))$. Then, as $n$ gets less than $32$, $n/3 + \lg n$ still less than $n$, so the remaining part is bounded by a constant.

The upper bound is then $\Theta(\lg n)$ too, and your bounds are tight.