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
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
O(n^(3/2)) time, and taking
log n for each look up).