Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.