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).
