# Is this divide-and-conquer algorithm O(n)?

Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline:

function solve(array, k):
if array shorter than k:
return default value
left = solve(left half of array, k)
right = solve(right half of array, k)
middle_crossing = combine(left half of array, right half of array, k)
return max(left, right, middle_crossing)

Make the array a "view" or a begin/end index pair, so passing an array half is O(1). And the combine operation takes O(k).

At first sight its structure looks like for example mergesort, so might take O(n log n). But it's faster for two reasons:

• The recursion doesn't go all the way down to length 1. Only to length k.
• The combine operation doesn't take O(n), only O(k).

So we have this runtime:

T(n) = { 2 * T(n/2) + O(k)    if n >= k
{ O(1)                 otherwise

I believe the total runtime is T(n) = O(n). One way to I think prove it:

We recurse only down to length k. So instead of finding the runtime T(n) as number of element-operations given n elements, consider the array of n elements as an array of n/k blocks of k elements each, and find the runtime B(n) as number of block-operations. Since each block-operation takes O(k) time, we have:

T(n) = B(n/k) * O(k)
B(m) = 2 * B(m/2) + O(1)

Master theorem (or just thinking) gives B(m) = O(m) and thus we have:

T(n) = B(n/k) * O(k) = O(n/k) * O(k) = O(n)

Is that right? Is it O(n), and is my proof correct? And does this "consider blocks" technique have a name (I haven't seen it before)? Or is there a better way to prove it?

• The idea is interesting, but one thing to beware of is that the constants may be different for each "block". So even if each block takes $O(m)$, summing them up could potentially not be $O(n)$. So in order to apply this technique you will have to be much more careful - I doubt it will be easier than using a standard technique. Oct 14, 2021 at 20:11
• @nirshahar You mean my O(k) in 2 * T(n/2) + O(k) and my O(1) in 2 * B(m/2) + O(1), right? I guess I was sloppy there. I see the master theorem says "f(n)" at that place, i.e., a certain fixed function. Don't know whether it does that because it talks about it. I thought that's how mine would be understood as well, always same constant. I could rewrite it with an f, it's true for the algorithm. I'd say something like that, and also showing such a "standard technique", would be good as an answer :-) Oct 14, 2021 at 20:33

You can easily compute the height $$h$$ and the total number of nodes in the recurrence tree. After $$h-1$$ levels, the size of the subproblem is at least $$k$$ and at most $$2k$$. Therefore, $$n/2^{h-1} \geq k$$ after $$h-1$$ levels. Thus, we get the height of the tree at most $$\log (n/k)+1$$. Furthermore, the total nodes in the recurrence tree is at most $$O(2^{\log n/k+1}) = O(n/k)$$.
At every node of the tree, the algorithm is doing $$O(k)$$ operations. Therefore, the overall running time is $$O(n)$$
• @don'ttalkjustcode Yes it is the same constant at every node. However, I am doubtful about your bucketing technique, i.e. T(n) = B(n/k) * O(k). Note that there are total $n-k$ buckets (or subarrays) technically, so I am not sure if the statement T(n) = B(n/k) * O(k). makes sense. Oct 14, 2021 at 21:15