I'm trying to make sense of the notes for my course.

It starts with block alignment.

He sets the block size to `(log(n))/4`

and shows that (with ATCG) we have lookup table size of `4^t * 4^t = n`

.

Then it is claimed that we can therefore build the lookup table in `O(n)`

. How can we build a lookup table of size `n`

in `O(n)`

unless we can compute alignments in constant time?

Then it states that we have `(n/t)^2`

blocks which is `n^2 / (log n)^2`

. This value is then multiplied by the `log(n)`

that it takes for each access to the table. Why does it take anything other than constant time to access a lookup table? Isn't the whole point of building a lookup table that you can access it in constant time?

This is then expanded to cover the LCS case but with the same arguments as above (building a table of size `n^(3/2)`

in `O(n^(3/2))`

time, and taking `log n`

for each look up).