# What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?

Is it true that some common forms of recursive T(n) can give the following conclusions?

When

T(n) = T(n/c) + b    where c is a constant > 1, b is any constant


then the algorithm is O(log n).

When

T(n) = T(n/c) + T(n/d) + bn   where c and d are constants > 1, b is any constant


then the algorithm is O(n log n).

When

T(n) = T(n - c) + bn   where c, b are constants > 1


then the algorithm is O(n2) and seems like many useful algorithms don't have this pattern and O(n2) is not often seen in classical algorithms.

I have seen the form:

T(n) = T(n/c) + T(n/d) + O(n)   where c and d are constants > 1


for the selection / median algorithm and it is concluded that the algorithm is O(n) but isn't the T(n) the same as formula 2 for O(n log n) above?

• Note that recurrences are not at all necessarily tied to algorithm runtimes. – Juho Aug 17 at 20:51
• Your question is answerable simply by taking the master theorem and playing around with different values. – dkaeae Aug 19 at 6:55