[Duaa Zahi]

Hello,
What is the complexity of the following algorithm?
if i try to plot the graph, the time am getting is zero!

#include <iostream>
#include <ctime>

using namespace std;

int prgm(int a[], int n, int x)
{
       int mid;
       int i = 0;
       while ( i < n ) {
               mid = ( n + i ) / 2;
               if ( a[mid] < x )
                       i = mid + 1;
               else if ( a[mid] > x )
                       n = mid;
			   else{
                       return mid;
			   }
	   }
       return 0;
}

int main ()
{
    int n=1000000, m=2;
	srand(time(0));
     cout<<"testing"<<endl;
    for (int i=0; i<6; i++) {
        n*=m; 
        int* a = new int [n];
        for (int i = 0; i<n; i++) a[i] = i;

		clock_t start, finish;  
        start=clock(); finish=clock();
        double clock_delay=(double)(finish - start);
	    int x = -1;
	    
  
        start=clock();

        prgm(a, n, x);

        finish=clock();

        double elapsed_time=(double)(finish - start) - clock_delay;
        double elapsed_second=elapsed_time / CLOCKS_PER_SEC;
        cout<<"D: x=" << x<< " n="<<n<<" time="<<(double)elapsed_second<<endl;
		delete []a;
    }
 cout<<"done"<<endl;
    return 0;
}

[blackcompe]

Do you know what the algorithm is?

[jjl]

The time complexity of a binary search algorithm can be described by the recurrance relation

T(n) = T(n/2) + 1

Solving this recurrence relation lead to finding the "Big Oh" of your algorithm.

Hint:
You can use telescoping to solve the recurrence relation, link below

http://en.wikipedia....escoping_series

[Duaa Zahi]

Thank you jjl..
and

Quote

Do you know what the algorithm is?

no i didn't know the algorithm until now.