0
$\begingroup$

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! :)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Ian
    Commented Apr 4, 2018 at 15:33

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .