255.What do you mean by complexity of an algorithm? Derive the asymptotic time
complexity of a non recursive, binary search algorithm. 

Ans:
The term complexity is used to describe the performance of an algorithm. Typically
performance is measured in terms of time or space. Space complexity of an
algorithm is the amount of memory is needed to run the algorithm. Time complexity
of an algorithm is the amount of computer time it needs to run the algorithm. Mostcommon notation for describing time complexity 0(f(n)), where n is the input size
and f is a function of n. An algorithm ~ 0(f(n)) means there exists N such that for all
n > N the run time of the algorithm is less than c.f(n), where c is a constant.
Binary search can be applied on a sorted array to search for a particular item.
Given array positions A[l], the search is conducted in the following way.
Binsearch (x, l,n)
{
L=l;
U = n;
While (L <= U)
{ mid = (L + U) / 2;
If (A[mid] = x)
Return.True;
Else
If (A[mid ] > x)
L = mid + 1;
Else
U = mid - 1;
}
return False;
}
Thus at each state the array is halved into two equal parts. In the worst case the
algorithm terminates when the portion of the array considered is of length 1, Thus if
n = 2 , in the worst case the while loop will have to repeat k times. Where k = log n.
Thus asymptotic complexity is O(log n).