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

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

-
Usually the argument of $T(\cdot)$ on the RHS is smaller than the one on the LHS - did you perhaps mean $T(n) = T(n/3) + \log(n)+1$? – gt6989b Mar 8 '13 at 5:21
yes. thank you! fixed it – Sara Meyer Mar 8 '13 at 5:22
Are you sure $\lg n$ goes inside the brackets like you wrote, $T(n/3+\lg n)+1$ and not outside, like $T(n/3) + \lg n + 1$? – gt6989b Mar 8 '13 at 5:24
yes, it does go inside the brackets – Sara Meyer Mar 8 '13 at 5:27
fixed it... No. – Did Mar 8 '13 at 16:19

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.

-

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.

-