2
$\begingroup$

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.

For linear search :

procedure Linear_search(a1,a2,...,an:integers,k)
1.location = 0;
2.for i = 1 to n      #n+1 times
3.    if (a_i = k)  then location = i # n times
4.return location;

so total comparisons are =n+n+1=(2n+1). Right?

For Binary Search and ternary search,we know the algorithm.But the number of comparisons are,

T(n) = T(n/2) + 2,  T(1) = 1
 T(n) = T(n/3) + 4, T(1) = 1

Hence solving this will give 2clogn + O(1) and 4clogn + O(1).

how to constants(2 ,4) are formed?? Also correct me if my comparsions are wrong.

$\endgroup$

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

0
$\begingroup$

When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$ comparisons in the worst case.

For binary search, at each step you are making a 3-way comparison between the middle element of the current segment of the array and the input element. The number of 3-way comparisons satisfies the recurrence $T(n) \leq T(\lceil \frac{n-1}{2} \rceil) + 1$, with base case $T(1) = 1$ (when $n = 1$, you are making a 2-way comparison). If you are only allowing 2-way comparisons, then each 3-way comparison has to be simulated using two 2-way comparisons, which might be the reason why the recurrence has $+2$ instead of $+1$.

For ternary search, you are making two 3-way comparisons (comparing the two middle thirds to the input element), which translates to four 2-way comparisons.

(A 2-way comparison is one which has two outcomes: for example, "$x = y$?" is a 2-way comparison, as is "$x \leq y$?". A 3-way comparison is one which has three outcomes: given two elements $x,y$, the comparison tells you whether $x < y$, or $x = y$, or $x > y$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.