1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Oct 14 at 20:11
  • $\begingroup$ @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 :-) $\endgroup$
    – no comment
    Oct 14 at 20:33
1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Yes, looks good now. I myself had handwavingly used something like "n/(2^h) is approximately k", good enough to fairly convince myself, but I appreciate seeing how it's done more precisely. $\endgroup$
    – no comment
    Oct 14 at 20:58
  • $\begingroup$ Have you seen nir shahar's comment and my reply under the question? I wonder whether the same issue applies to your "At every node of the tree, the algorithm is doing O(k) operations". Or is your usage ok, different because you say "O(k)" once, from kind of a "global outside perspective" rather than inside the recurrence relation, so it's clearer that it means the same constant at every node? $\endgroup$
    – no comment
    Oct 14 at 21:03
  • $\begingroup$ @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. $\endgroup$ Oct 14 at 21:15
  • $\begingroup$ Yes, I know we both mean the same constant at every node. My question is whether that is understood that way. I'm not sure whether/where it needs to be stated explicitly. $\endgroup$
    – no comment
    Oct 14 at 21:55
  • 1
    $\begingroup$ Yeah, that's why I said "lowest workful level", meaning the lowest level where real work is done (i.e., not the "return default value" branch). And technically, everything that is O(1) is also O(k), so it's not really wrong. But yes, in my proof I rather ignored these trivial calls/nodes, as I think it's clear that their O(1) time doesn't matter. I also could've written the pseudocode to actually not do another recursive call at all if the half array is too short. (Btw not trying to "defend" my proof, just explaining my thoughts. I appreciate you pointing out what's not good.) $\endgroup$
    – no comment
    Oct 14 at 22:33

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.