I have the following algorithmic problem:
Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.
Watson-Crick palindromes are strings whose reversed complement is the original string. The complement is defined letter-wise, inspired by DNA: A is the complement of T and C is the complement of G. A simple example for a WC-palindrome is ACGT.
I've come up with two ways of solving this.
One requires $\mathcal{O}(n)$ space.
- Once the machine is done reading the input. The input tape must be copied to the work tape in reverse order.
- The machine will then read the input and work tapes from the left and compare each entry to verify the cell in the work tape is the compliment of the cell in the input. This requires $\mathcal{O}(n)$ space.
The other requires $\mathcal{O}(\log n)$ space.
- While reading the input. Count the number of entries on the input tape.
- When the input tape is done reading
- copy the complement of the letter onto the work tape
- copy the letter L to the end of the work tape
- (Loop point)If the counter = 0, clear the worktape and write yes, then halt
- If the input tape reads L
- Move the input head to the left by the number of times indicated by the counter (requires a second counter)
- If the input tape reads R
- Move the input head to the right by the number of times indicated by the counter (requires a second counter)
- If the cell that holds the value on the worktape matches the current cell on the input tape
- decrement the counter by two
- Move one to the left or right depending if R or L is on the worktape respectively
- copy the Complement of L or R to the worktape in place of the current L or R
- continue the loop
- If values dont match, clear the worktape and write no, then halt
This comes out to about $2\log n+2$ space for storing both counters, the current complement, and the value L or R.
My issue
The first one requires both linear time and space. The second one requires $\frac{n^2}{2}$ time and $\log n$ space. I was given the problem from the quote and came up with these two approaches, but I don't know which one to go with. I just need to give the space complexity of the problem.
The reason I'm confused
I would tend to say the second one is the best option since it's better in terms of time, but that answer only comes from me getting lucky and coming up with an algorithm. It seems like if I want to give the space complexity of something, it wouldn't require luck in coming up with the right algorithm. Am I missing something? Should I even be coming up with a solution to the problem to answer the space complexity?