Questions & Answers of Searching

Weightage of Searching

Total 3 Questions have been asked from Searching topic of Algorithms subject in previous GATE papers. Average marks 1.67.

Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The Problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is 0(na logbn + mc logdn), the value of a + 10b + 100c + 1000d is ____.

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?