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! 🙂
Best Answer
The exact solution, which you have, by definition gives the tightest bounds.
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)$.