When you are given a problem statement there will be an input.The given input has to be countable in some way. In order to get the answer or output you got to manipulate the input in some way are the other in programming. The question is ,how many operation are you going to do on your inputs ... it depends on problem requirement .
For example : In an sorted array of n elements .
1)searching can be done by checking each and every element .
2)And using the mathematical property that array is sorted you apply a very old trick
called binary search .which divedes our search space into half every time we check
our trick. This reduces our search space so as reducing the operations.
please read Master theorem to know how to evaluate complexity.
In the case 1 we have complexity in big oh notation as O(n) where n is the input .
In the case 2 we have complexity in big oh notation as O(log(n)) where n is the input .
For basic please refer Big Oh
Coming to the recursion , Suppose our problem be searching, let us consider the binary search .
int binary_search(int A, int key, int imin, int imax)
// test if array is empty
if (imax < imin):
// set is empty, so return value showing not found
// calculate midpoint to cut set in half
int imid = midpoint(imin, imax);
// three-way comparison
if (A[imid] > key)
// key is in lower subset
return binary_search(A, key, imin, imid-1);
else if (A[imid] < key)
// key is in upper subset
return binary_search(A, key, imid+1, imax);
// key has been found
Firstly for searching an element say X in our input length N then we check middle element in an sorted array to see whether element to be searched(x) is greater or lesser .If it is greater we search the element from middle element(n/2) to last element N recursively .If element to be search(x) is smaller than middle we search from 1 to (n/2) ,as we know that element after middle element is bigger than middle(x