When can you ignore certain numbers in a recurrence relation?

Question

I am trying to understand how to work out time complexities given certain recurrence relation, however I know that in certain recurrence relation some numbers can be omitted since they make no difference when $n$ gets very large. The problem i'm having is being able to identify the numbers that can be omitted.

For example

$T(n) = 3T(n/3 - 2) + n/2$ Can we omit the 2's here and use the master theorem on

$T(n)=3T(n/3) + n$ ?

What about the following

$T(n) = T(n-2) + n^2$ can we say that $T(n) = T(n) + n^2$ and once again use the master theorem?

Not really clear to me when it is OK to omit numbers.

Answer 1

It depends on what you want to reach and on the recurrence relation.

For example, consider the following recurrence relation $$T(n) = T(n/2 - 1) + 6n, T(1) =1$$ and assume we are interested on its asymptotic growth. If we remove the factors $\frac{1}{2}$ in $T(n/2 - 1)$ and $6$ from $6n$ then we have the following relation

$$T(n) = T(n-1) + n$$ that is a closed formula for the sum of the first $n$ positive integers and is $\Theta(n^2)$.

If we omit only $-1$, then we are left with
$$T(n) = T(n/2) + 6n$$ which is $O(n)$. Thus, omitting factors may result in asymptotically different recurrence relations.

As for your examples, $T(n) = 3T(n/3 - 2) + n/2$ is clearly less than or equal to $T(n)=3T(n/3) + n$, so in order to obtain an upper bound for $3T(n/3 - 2) + n/2$ you can use the later relation, but their exact values for each $n$ is certainly differ. However, I don't see any meaning in the relation $T(n) = T(n) + n^2$ unless $n=0$.