Is this a divide-and-conquer algorithm?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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