Store 1 million Integers in An Array To search an element in that array and find out its time complexity (best, worst, and average)
Program
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define sf(x)
#define pf(x)
#define pfn(x)
#define pfc(x)
#define f(i,x,y)
#define fi(i,x,y,inc)
#define rf(i,x,y)
scanf("%d", &x)
printf("%d ", x)
printf("%d\n", x)
printf("%d, ", x)
for(int i = x; i < y; i++)
for(int i = x; i < y; i += inc)
for(int i = x; i >= y; i--)
void c_() {
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\KIIT\\input", "r", stdin);
freopen("C:\\Users\\KIIT\\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;
}
else
{
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;
}
else
{
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;
}
else
{
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
Tags:
DAA