I'd like to know if I have the right intuition and my answer is headed the correct way. I am given a function $ f = \{0, 1\}* \rightarrow \{0, 1\}* $ that is computable in space O(log n) assume that for every $x \epsilon \{0, 1\}*, |f(x)| = |x|$ The language $L = \{ x\#y | \ x, y \epsilon \{0, 1\}*, |x| = |y|, \ and \ f(x) = f(y)\} L \ \epsilon \ SPACE(log\ n)$ I am suppose to prove that $ L \ \epsilon \ SPACE(log\ n) $ Please correct me if my intuition is incorrect. My solution would be to build a decider M which is a turing machine. M takes inputs x and y, run the function f on input x and y and if the lengths of the two strings are equal then accept, otherwise reject. Now the turing machine runs in $ O(log n) $ because the function f is computable in $ O(log n) + O(log n) = O(log n) $ and comparing the length returned by the function is $ O(1) $ Thus the language is decidable by a turing machine that is run in $ O(log n) $ and only takes Space $ O(log n) $