# Find tight asymptotic upper bound for T(n)

How do I find the tightest asymptotic upper bound of $T(n) = T(n-3) + 3$

Assuming $T(n) = n$ for $n \le 4$

I don't quite understand what I have to do here, is my solution supposed to be in big-o notation or something else? If it is big-o notation, how can I make it tighter than $O(n)$, which is its complexity class, right?

I thought I might need to use the substitution method, but that just gives me $T(n) = n$ which we already know.

Any help would be much appreciated, thanks in advance! :)

• Generally you want the tightest bound you can get, or sometimes the tightest bound you can get that is not so cumbersome that it is annoying to work with it. If you can get the exact solution and the exact solution is simple (like it is here) then that's definitely going to be the best possible bound.
– Ian
Commented Apr 4, 2018 at 15:33

The only time you might want to modify the exact solution is when it is more complicated than you like. For example, you might replace $n^2+n\log n$ by $O(n^2)$ or $\Theta(n^2)$.