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. Most common 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.