patternMinor
Master theorem for $T(n)=T(n-1)+O(n)$
Viewed 0 times
masterfortheorem
Problem
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.
$$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.
Solution
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.
$$ \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.
Context
StackExchange Computer Science Q#89828, answer score: 7
Revisions (0)
No revisions yet.