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

Question

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?

Answer 1

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