DAA - C program to Calculate time Complexity using Binary Search 1 million integers in Array

WAP in C to store 1 million integers in an array. To search an element in that array and find out its time complexity using binary search (Best Case, Worst Case, and Average Case)

Program

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define sf(x) scanf("%d", &x)
#define pf(x) printf("%d ", x)
#define pfn(x) printf("%d\n", x)
#define pfc(x) printf("%d, ", x)
#define f(i,x,y) for(int i = x; i < y; i++)
#define fi(i,x,y,inc) for(int i = x; i < y; i += inc)
#define rf(i,x,y) for(int i = x; i >= y; i--)
void c_() {
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\XYZ\\input", "r", stdin);
freopen("C:\\Users\\XYZ\\output", "w", stdout);
#endif
}
int main() {
c_();
int n = 100000;
int arr[n];
f(i, 0, n) {
//arr[i] = 1 + rand() % 100;
arr[i] = i + 1;
}
int best = arr[(n - 1) / 2];
int worst = arr[1];
int avg = arr[n / 16];
time_t strt, end;
int lo = 0, hi = n - 1;
strt = clock();
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (arr[mid] == best) {
end = clock();
double t = end - strt;
printf("Time taken for best case: %f\n", (t /
CLOCKS_PER_SEC));
break;
}
if (arr[mid] > best)
{
hi = mid;
}e
lse
{
lo = mid + 1;
}
}
lo = 0, hi = n - 1;
strt = clock();
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (arr[mid] == avg) {
end = clock();
double t = end - strt;
printf("Time taken for avg case: %f\n", (t /
CLOCKS_PER_SEC));
break;
}
if (arr[mid] > avg)
{
hi = mid;
}e
lse
{
lo = mid + 1;
}
}
lo = 0, hi = n - 1;
strt = clock();
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (arr[mid] == worst) {
end = clock();
double t = end - strt;
printf("Time taken for worst case: %f\n", (t /
CLOCKS_PER_SEC));
break;
}
if (arr[mid] > worst)
{
hi = mid;
}e
lse
{
lo = mid + 1;
}
}
return 0;
}

Output

Time taken for best case: 0.000003

Time taken for avg case: 0.000001

Time taken for worst case: 0.000002

     Draw the graph as the time found in each case:

Sl No.	No.	of	Time Complexity	Time Comp		Time Complexity
	element		( Best Case)	(Worst Case)		(Average Case)
1	5000		0.000001	0.000001		0.000001
2	10000		0.000001	0.000002		0.000003
3	15000		0.000001	0.000004		0.000004
4	20000		0.000002	0.000004		0.000004
5	25000		0.000002	0.000005		0.000005
6	30000		0.000002	0.000006		0.000005

Graph For Best Case Worst Case and Average Case