What is the run time complexity between recursive binary search algorithm and non recursive binary search algorithm
Answers
Answer:
Complexity Analysis of Binary Search
Complexities like O(1) and O(n) are simple to understand. O(1) means it requires constant time to perform operations like to reach an element in constant time as in case of dictionary and O(n) means, it depends on the value of n to perform operations such as searching an element in an array of n elements.
But for O(Log n), it is not that simple. Let us discuss this with the help of Binary Search Algorithm whose complexity is O(log n).
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Explanation:
Mark as brain list
Follow me