Home » MCQs » Algorithms MCQs

What is the auxiliary space complexity of the space-optimized bottom-up approach for LCS?

37. What is the auxiliary space complexity of the space-optimized bottom-up approach for LCS?

1. O(m * n)
2. O(n)
3. O(1)
4. O(m)

Answer

The correct answer is: B) O(n)

Explanation

The space-optimized approach uses two arrays of size n, where n is the length of one of the strings.