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


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

then the algorithm is O(log n).


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


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?

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

Your Answer

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

Browse other questions tagged or ask your own question.