The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence

$$T(n) = aT(n/b) + f(n),$$

where $a \ge 1$ and $b > 1$. But for selection sort, $b=1$. I am trying to apply the master theorem and stuck.

  • $\begingroup$ Are you sure this question isn't already answered on this site? Please try to have a look $\endgroup$ – Discrete lizard Mar 26 '18 at 18:46
  • $\begingroup$ Possible duplicate of Running time of selection sort $\endgroup$ – Discrete lizard Mar 26 '18 at 18:46
  • $\begingroup$ Nope. It is not the answer to my question. $\endgroup$ – Emrah Sarıboz Mar 26 '18 at 18:47
  • 2
    $\begingroup$ Simple; the Master Theorem doesn't apply to this problem. $\endgroup$ – Rick Decker Mar 26 '18 at 20:19
  • 2
    $\begingroup$ I think you answered your own question. What would $a$ and $b$ be? In this case, solve the recurrence directly (using the real cost function, not that O(n) bound). $\endgroup$ – Raphael Mar 26 '18 at 20:22

The master theorem isn't the appropriate theorem for every recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the well-known identity $$ \sum_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2). $$ You should think of the master theorem as a tool, not a liability. It is supposed to help you – use it if you need it, but feel free to use any other approach as you see fit. The only cases you absolutely have to apply the master theorem is when answering questions on a homework or a test that say you must use it; in the real world one tends not to limit oneself.

| cite | improve this answer | |
  • $\begingroup$ This is what I was looking for! Thanks! $\endgroup$ – Emrah Sarıboz Mar 27 '18 at 15:31

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.