3 Replies - 237 Views - Last Post: 07 October 2012 - 10:05 PM Rate Topic: -----

#1 Duaa Zahi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 19-March 12

What is the Complexity ?

Posted 07 October 2012 - 03:21 PM

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;
}




Is This A Good Question/Topic? 0
  • +

Replies To: What is the Complexity ?

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1131
  • View blog
  • Posts: 2,484
  • Joined: 05-May 05

Re: What is the Complexity ?

Posted 07 October 2012 - 05:05 PM

Do you know what the algorithm is?
Was This Post Helpful? 0
  • +
  • -

#3 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1046
  • View blog
  • Posts: 4,449
  • Joined: 09-June 09

Re: What is the Complexity ?

Posted 07 October 2012 - 05:43 PM

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
Was This Post Helpful? 1
  • +
  • -

#4 Duaa Zahi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 19-March 12

Re: What is the Complexity ?

Posted 07 October 2012 - 10:05 PM

Thank you jjl..
and

Quote

Do you know what the algorithm is?

no i didn't know the algorithm until now.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1