Question
Binary Search is an efficient searching algorithm that follows the Divide and Conquer approach. What is its time complexity?
Solution
Binary Search repeatedly halves the search space. If the input size is N, after one comparison, the problem size becomes N/2. After two comparisons, it's N/4, and so on. This logarithmic reduction in search space leads to a time complexity of O(log N).
More IT Operating System Questions
- When evaluating the performance of an algorithm, which of the following factors is generally considered most important for large input sizes?
- In public key cryptography ___ key is used for encryption and ____ key is used for decryption.
- You have a list of numbers and need to find the maximum value. Which of the following approaches would be the most efficient in terms of time complexity?
- Stack is sometimes called as :
- What mechanism is primarily responsible for managing the sequence of function calls and their local variables in a recursive function?
- What is a key characteristic regarding negative edge weights in the Floyd-Warshall algorithm?
- What is the best case time complexity of merge sort?
- Which of the following statements accurately describes hard computing?
- Which algorithm is commonly used for Part-of-Speech tagging?
- In data analysis, a "sparse matrix" is often used. What is the defining characteristic of a sparse matrix?
