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?
- O(n^2)
- O(n^1.59)
- O(n log n)
- 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).