# number of comparisons in searching algorithms

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.

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$$.
(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$$.)