Data Structure And Algorithm : Practice Questions and Answers

Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.

Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.

Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.

Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).

In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.

Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.

In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.

Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.

Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won't start searching from index 0.

This gives a very slight improvement as you are skipping the first k elements.

Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8

With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.

Trace with respect to the make_delta function, always note that the last element is always 0.

Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.

The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)). Linear search is easy to implement and understand than other searching techniques.

Although ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at first position or at last position.

Worst case is when the desired element is at the tail of the array or not present at all, in this case you have to traverse till the end of the array, hence the complexity is O(n).

The element is at the head of the array, hence O(1).

It is practical to implement linear search in the situations mentioned in When the list has only a few elements and When performing a single search in an unordered list, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.

Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).