Home » MCQs » Algorithms MCQs

What is the time complexity of the Karatsuba algorithm for multiplying two binary strings?

21. What is the time complexity of the Karatsuba algorithm for multiplying two binary strings?

1. O(n^2)
2. O(n^1.59)
3. O(n log n)
4. O(n)

Answer

The correct answer is: B) O(n^1.59)

Explanation

The Karatsuba algorithm uses divide-and-conquer to reduce the number of required multiplications, leading to an O time complexity (n^1.59).