I am reading about the Four Russians algorithm. Let D be the dynamic programming algorithm that is filled during the edit distance problem. We assume that the edit operations cost unit time each. We partition D into small blocks each of width and height equal to t, where t is fixed in the analysis. Each such block is called a t-block. D is divided into t-blocks such that any two adjacent t-blocks overlap by either a row or column of width ( or height ) equal to t. After this partitioning is done, the Four Russians algorithm fills up D block by block.
After partitioning D into t-blocks we have n^2/t^2 blocks and if processing of each of the blocks takes O(t) time then the running time of the algorithm is O(n^2/t).
How can the processing of each of the blocks take O(t)-time, given that one block contains t^2 cells?
How is that related to bioinformatics ? It looks like you've already posted the same question on Computer Science Stack Exchange.