Talk:Hirschberg's algorithm

Template:WikiProject Computational Biology

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

???

This article has not yet received a rating on Wikipedia's content assessment scale.

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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:

It is generally accepted that Hirschberg's algorithm takes linear space.
Juri Master's original work to claim O(n + m) is mistaken. The claim would need to be O(n + log₂(m)).
The algorithm does not need to put any elements from m or n on the stack.
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.
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.
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)[reply]

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)[reply]