//Order of Magnitude //O(1) //O(log n) //O(n) int a[10]={0,1,2,3,4,5,6,7,8,9}; ///Constant time - O(1) - perform the same amount of work regardless of the size of the input set n. int findfirst(int n){ int ret=-1; ret=a[0]; return ret; } int findlast(int n){ int ret=-1; ret=a[n]; return ret; } //Logarithmic time- O(log n) -work performed is proportional to the lg base 2 of the size of the input set n. int findnth_ver2(int n,int x){ int ret=-1; int i,mid=0,high=0,low=0; high=n-1; while(low <= high){ mid=(low+high)/2; if( a[mid] < x ) low=mid+1; else if (a[mid] > x) high=mid-1; else return mid; } return ret; } // Linear time - O(n)-work performed is proportional to the size of the input set n. int findnth_ver1(int n,int x){ int ret=-1; int i; for (i=0;i < n;i++) if(a[i]==x){ ret=i; break; } return ret; } int main(){ int n=10; printf("\n Find first : %d",findfirst(0)); printf("\n Find last : %d",findlast(n-1)); printf("\n Find nth ver1: %d",findnth_ver1(n,5)); printf("\n Find nth ver2: %d",findnth_ver2(n,5)); }