0
$\begingroup$

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added):

2.3.2 Analyzing divide-and-conquer algorithms

[...]

A recurrence for the running time of a divide-and-conquer algorithm falls out from the three steps of the basic method. As we did for insertion sort, let $T(n)$ be the worst-case running time on a problem of size $n$. If the problem size is small enough, say $n \leq n_0$ for some constant $n_0 > 0$, the straightforward solution takes constant time, which we write as $\Theta(1)$.

(I was not able to find a Google Books preview of §2.3.2, but the 3rd edition version of the section can be found here.)

I'm a little confused as to what "straightforward solution" is referring to. I initially thought it was the base case, but can't be sure (why didn't the authors just use the term "base case"?).

My lecture slides also seem to think the authors are referring to the base case, but use the term "brute-force solution" in place of "straightforward solution". Here's the text from the relevant slide (emphasis added):

$T(n)$ = running time on a problem of size $n$ If a problem is small enough (say, $n \leq c$ for some constant $c$), we have a base case. The brute-force solution takes constant time: $\Theta(1)$.

  • What exactly are the terms "straightforward solution" and "brute-force solution" referring to?
  • If they are referring to the base case, how can we be sure that the base case will take $\Theta(1)$ time? Is it possible for the base case to be non-trivial so that we spend a non-constant amount of time in it?
$\endgroup$

2 Answers 2

0
$\begingroup$

Yes, "straightforward solution" refers to the base case (and also "brute-force solution" on your slides). You need at least one base case (there could be more than one in some cases), otherwise recursion never ends and your recurrence equation is wrong. Now, the base case is often assumed to require $O(1)$ (constant time), since it is associate to a very small - actually a constant - number of elements (or objects, items etc). Think about a sorting algorithm designed using divide and conquer. Le $n$ be the size of the array in one recursive invocation. Two possible base cases may be $n=1$ (because if your array only includes one element, then it is already sorted) and $n=2$ (because for two elements one comparison is enough to establish the correct sorted order).

$\endgroup$
0
$\begingroup$

The straightforward solution is an easy but possibly inefficient solution, such as the one you can design for a small number of elements (e.g. sorting 1, 2 or 3 elements).

The brute-force solution is a particular case of straightforward solution, which tries all possibilities without caring for efficiency (for instance trying all permutations until you get an increasing sequence).

If these solutions are used to solve the cases $n<n_0$, then they indeed correspond to the base case of the recurrence. As $n_0$ is a constant, the running time for $n<n_0$is perforce bounded, i.e. constant in the asymptotic sense.

E.g. real-world implementations of Quicksort often switch to StraightSelection or similar for $n<10$ (say). But you may not conclude that the complexity is $O(n^2)$ because $n<10$; the complexity is constant, bounded by $T_{\text{StraightSelection}}(10)$.


One might think of cases such that we use divide & conquer down to some $n_0$ that is a function of the initial $n$, then switch to a straightforward solution. In this case, the complexity associated to the straightforward solution would not be a constant, though it can still be the base case. But honestly, I have never met such a construction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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