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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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