Talk:Hirschberg's algorithm

Untitled

I am starting this article. I need to add a section on the proof of time and space complexity. Vegasprof 01:18, 21 March 2007 (UTC)

---

I'm not sure what this line in the pseudocode is doing:

 ArgMin{Edit[x^left,Pref[y,cut]] + Edit[x^right,Suff[y,n-cut]]}

Are those meant to be two array slices? What's the '+' operator doing there? Kenahoo (talk) 23:47, 24 November 2009 (UTC)

Space necessary for Hirschberg's algorithm

On 3 July 2011, user Juri Master changed the space calculation from O(min{m,n}) to O(n + m) arguing that the stack space to make recursive calls uses hidden memory. This should be changed back because:

1. It is generally accepted that Hirschberg's algorithm takes linear space.
2. Juri Master's original work to claim O(n + m) is mistaken. The claim would need to be O(n + log₂(m)).
3. The algorithm does not need to put any elements from m or n on the stack.
4. log₂(m) is small enough that it is not significant. If m were 1,000,000,000,000 (1 trillion), then log₂(m) rounds up to 40. A common implementation of the algorithm would require passing four integers, two pointers, and a return address on the stack. If they were each 64 bits that amounts to 56 bytes per recursive call, or just over 2KB to handle 1 trillion records. In contrast, Hirschberg's algorithm would require 8TB(!) to run the forward (or reverse) subprogram on 1 trillion records. In any interesting problem log₂(m) will be dwarfed by n.
5. Hirschberg's algorithm can actually take O(2n) space since the output uses an additional n space. That could be much larger than O(n + log₂(m)) space.
6. Big-O notation is only interested in how computational complexity scales. Hirschberg's algorithm actually takes O(2mn) time but the two is dropped because it doesn't affect how the algorithm scales. For the same reason, O(n + log₂(m)) should lose the log₂(m). — Preceding unsigned comment added by 204.246.125.93 (talk) 06:15, 31 July 2011 (UTC)

There is a bit of confusion here because we are talking about scaling for an algorithm with 2 inputs. Often you would just concatenate the inputs (q = n + m) and then calculate the scaling, in which case it would take O(q) space. Since we are keeping the inputs separate, would the actual scaling not be O(min{ max{m, log(n)}, max{log(m), n} })? This is because we aren't guaranteed that the log of the longer input is smaller than the shorter input. In short, O(q+log(q))==O(q), but O(m+log(n))!=O(m). I agree that in most cases this is negligible (point 4 above).

Pseudocode

I have a question about the pseudocode: For example in the forwards subprogramm in line 4 "Edit[Prefix[0,0]] = 0;":

Do i understand it correctly that Edit is an two-dimensional array? Why is it in line 4 only one index (Prefix[0,0])? It is a little bit confusing.

Volneb83 (talk) 18:21, 12 June 2012 (UTC)