1
$\begingroup$

I'd like to start by stating this isn't homework! I'm studying for a job interview and would appreciate a second opinion. (Well, I guess it is homework, but not for school!).

I've written an algorithm (see pseudocode below) to merge two sorted lists into one sorted list. The problem requires that I implement it as a recursive divide-and-conquer algorithm. My algorithm is recursive and works but does it count as divide-and-conquer?

The reason I'm asking is that the other people working on the same problem insist D&C must divide the lists in half every time and have $O(n \log n)$ complexity, like quicksort and mergesort. My algorithm doesn't divide the lists in the middle and has a complexity of $O(n+m)$ (where $n$ and $m$ are the lengths of the lists).

To summarize my question: Does a D&C algorithm have to have $O(n \log n)$ complexity and divide the problem in half every time? Or does this algorithm count as D&C?

merge_sorted_lists(list1, list2)
    if(list1 and list2 are empty)
        return empty list

    if(list1 is empty)
        return list2

    else if(list2 is empty)
        return list1

    else if(head of list1 < head of list2)
        smaller = pop head of list1

    else if(head of list2 < head of list1)
        smaller = pop head of list2

    return smaller + merge_sorted_lists(list1, list2)

P.S. I've implemented the algorithm in Java and it works.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I don't know that divide & conquer is a very precise notion. In particular, the "definition" given by your co-workers is bogus. $\endgroup$ – Raphael♦ Mar 14 '13 at 7:40
  • $\begingroup$ Are you sure you are supposed to solve merging with d&c, not the whole sorting? $\endgroup$ – Raphael♦ Mar 14 '13 at 7:52
  • $\begingroup$ Yes. The input lists are pre-sorted. Merging them recursively seems unnecessary, but it is a contrived problem. $\endgroup$ – Barry Fruitman Mar 14 '13 at 15:13
  • $\begingroup$ In that case, I wonder whether the questioner gave you an ill-posed problem on purpose; they might get more out of your attempts and arguments (see your co-workers' bogus argument) than from a straight-forward solvable problem. $\endgroup$ – Raphael♦ Mar 14 '13 at 15:29
  • 2
    $\begingroup$ See my answer; one can understand inductive algorithms as special case of divide & conquer, but for sake of semantics most people will want to have a "lower bound" on the notion. (Your proposed algorithm -- apply sorting -- is simple, but asymptotically slower than what you do in the question.) $\endgroup$ – Raphael♦ Mar 14 '13 at 17:11
6
$\begingroup$

"Divide & Conquer" is not a very fixed notion. It usually goes along the lines of

D&C algorithms divide the problem and solve recursively.

That's not very strong, for the following reasons.

  • What I would call inductive algorithms do this, but are usually not considered divide & conquer algorithms. Given a problem of size $n$, inductive algorithms solve subproblems (typically one) of size $n-c$ for some constant $c$ and derive a solution for the original problem. See here for an example.

  • Dynamic programming does exactly that, but it's not usually considered d&c. The difference is that in DP, subproblems overlap, which they don't in d&c. Also, we often don't know which subproblem is the "right" one, so we try out all possible partitionings (which causes overlapping).

Now, one might say that inductive and d&c algorithms are orthogonal special cases of dynamic programming, but that's for another discussion.

In order to "define" divide & conquer against those other types of algorithms, consider this:

D&C algorithms divide the problem of size $n$ into non-overlapping¹ subproblems of size $\frac{n}{c}$, solves (some of²) them recursively and combines the solutions to a solution of the original problem.

By this "definition", your algorithm is not divide & conquer.

As for runtimes, d&q algorithms can typically be analysed (roughly) using the master theorem. As you can see from the three cases, all kinds of runtimes of the form $n^a\log^bn$ can result, depending on the quality of the division and the runtime of the combining step.

  1. As I write the part about runtimes, it occurs to me that this may be too strong. Overlaps by a constant (sized part) are fine.
  2. Binary search can be considered the ultimate divide & conquer: by dividing cleverly, combining is unnecessary.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Note that the "definition" I offer may be too restrictive; algorithms leading to Akra-Bazzi-style runtime recurrences may very well be considered divide & conquer. $\endgroup$ – Raphael♦ Mar 14 '13 at 15:30
4
$\begingroup$

Does a D&C algorithm have to have O(nlogn) complexity and divide the problem in half every time?

No.

Consider Karatsuba's multiplication algorithm. Given two $n$-bit integers $x$ and $y$, the algorithm multiplies them as follows:

a = x >> n/2; 
b = x - (a << n/2);
c = y >> n/2;
d = y - (c << n/2);

u = a*c           // recurse!
v = (a+b)*(c+d)   // recurse!
w = b*d           // recurse!

return (u << n) + ((v-u-w) << n/2) + w

The algorithm reduces one $n$-bit multiplication to three recursive $n/2$-bit multiplications, using $O(n)$ time for the various additions, subtractions, and shifts. Thus, the running time of the algorithm satisfies the recurrence $T(n) = 3T(n/2) + O(n)$, whose solution is $O(n^{\lg 3}) = O(n^{1.585})$. In particular, the running time is not $O(n\log n)$.

In this example, the problem is divided "in half" in every recursive call, but that's not a requirement, either. A more complex generalization of Karatsuba's algorithm, due to Toom and Cook, uses five recursive $n/3$-bit multiplications, to get a running time of $O(n^{\log_3 5}) = O(n^{1.465})$.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

Your algorithm, while recursive, is not really D&C.

An algorithm is usually referred to as D&C if it solves the problem by dividing the instance into smaller instances of the same problem, and solving each smaller part using the same algorithm. The division does not have to be into two parts (and in particular not to two equal parts), nor does it have to run in $O(n\log n)$.

Dividing to halves and running in $O(n\log n)$ happens in Merge Sort, which is one of the most famous examples of D&C. Perhaps this is the source of your confusion.

The reason your algorithm is not really D&C is because you don't really divide the problem. Indeed, you handle the "edge" of the problem, and then use recursion to solve what's left.

By the way, observe that your algorithm just merges sorted lists, as you said. This algorithm is usually used as the "conquer" part of Merge Sort. If you incorporate it into a recursive algorithm that sorts, you get Merge Sort, and the running time of $O(n\log n)$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Your "definition" does not separate D&C from either inductive algorithms or dynamic programming. $\endgroup$ – Raphael♦ Mar 14 '13 at 7:42
  • 1
    $\begingroup$ I don't entirely agree - in a dynamic-programming algorithm you can't say that you use the "same algorithm" to solve the sub-problem (e.g. you use an inner loop which behaves the same). Same goes for inductive algorithms. But I wasn't aiming at a definition, and specifically not a sufficient and necessary condition. Just enough to answer this concrete question. $\endgroup$ – Shaull Mar 14 '13 at 8:11
  • $\begingroup$ Both inductive and dynamic programming algorithms (as I know them) are based on recurrences, so yea, you employ the same algorithm. The typical table-filling memoisation scheme for DP is "only" a neat trick that simplifies computation that does not change the concept underlying it. $\endgroup$ – Raphael♦ Mar 14 '13 at 14:28
  • 1
    $\begingroup$ Fair enough. Informally, though, I think that there is a linguistic point here: "Divide" implies that the parts you get are non-overlapping (e.g. divide an apple). Furthermore, the relation to "division" in the basic mathematical sense may imply that you actually divide the problem as $\frac{n}{c}$, as you state in your answer. So while I agree that my description is informal (and may even be misleading), its most intuitive interpretation is the correct formal definition. $\endgroup$ – Shaull Mar 14 '13 at 14:42
  • 1
    $\begingroup$ I see. I would agree, but I guess most would call "master theorem" algorithms d&c, and not all of those "divide" in your sense. Or consider Akra-Bazzi... $\endgroup$ – Raphael♦ Mar 14 '13 at 15:27
0
$\begingroup$

Let's say you have two lists A and B of length n, where n is even.

Merge the first half of A with the first half of B, giving an array X.

Merge the second half of A with the second half of B, giving an array Y.

Merge the second half of X with the first half of Y, giving an array Z.

The result is (first half of X) followed by Z followed by (second half of Y).

This is an awful algorithm, doing a job that can easily be done in $O (n)$ but using $O (n^{1.585})$ steps instead. Just as Karatsuba's multiplication algorithm, but without having any good excuse :-) But if you want a recursive divide-and-conquer algorithm, you got it. (If n is odd, add a huge number at the end of each list, merge them, remove the two huge numbers at the end of the list).

|cite|improve this answer
$\endgroup$

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.