# What is the Complexity ?

Page 1 of 1

## 3 Replies - 419 Views - Last Post: 07 October 2012 - 10:05 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294666&amp;s=233a28cbfa80043181d8164166a44101&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Duaa Zahi

Reputation: 0
• 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

• D.I.C Lover

Reputation: 1156
• Posts: 2,538
• Joined: 05-May 05

## Re: What is the Complexity ?

Posted 07 October 2012 - 05:05 PM

Do you know what the algorithm is?

### #3 jjl

• Engineer

Reputation: 1120
• Posts: 4,647
• 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

### #4 Duaa Zahi

Reputation: 0
• 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.