Question

Write a program to implement problem statement below:

provide the menu for input N and number of experiment M to calculate average time on M runs. randomly generated list. State your estimate on the BigO number of your algorithm/program logic. (we discussed in the class) Measure the performance of your program by given different N with randomly generated list with multiple experiment of Ns against time to draw the BigO graph (using excel) we discussed during the lecture. Lab-08-BigBiggerBiggtest.png *** high level of algorithm for measurement,

Step1. Given N>0, M >0, Input N, M, set C=M

Step2. While C is greater than 0, repeat Step 3 to 8

Step3. Fill the Array[N] with random number

Step4. record start time

Step5. call biggest(Array[N] return the biggest number and position

Step6. record end time

Step7. decrement C

Step8, running time[C] = end time - start time

Step9, Calculate average running time based on running time[M]

Step10. Record N and average running time into 2D Array *** use of clock function for benchmarking measure in milliseconds, http://en.cppreference.com/w/cpp/chrono/c/clock (Links to an external site.) *** you should use 2D array to store your experiment time with different N. biggest-example.rtf

Programming language: C++

Answer 1

#include<iostream>

#include<ctime>

#include<bits/stdc++.h>

using namespace std;

double calculate(double arr[], int l)

{

double avg=0.0;

int x;

for(x=0;x<l;x++)

{

avg+=arr[x];

}

avg/=l;

return avg;

}

int biggest(int arr[], int n)

{

int x,idx,big=-1;

for(x=0;x<n;x++)
{

if(arr[x]>big)
{

big=arr[x];

idx=x;

}

}

return idx;

}

int main()

{

vector<pair<int,double> >result;

cout<<"Enter 1 for iteration\nEnter 2 for exit\n";

int choice;

cin>>choice;

while(choice!=2)

{

int n,m;

cout<<"Enter N"<<endl;

cin>>n;

cout<<"Enter M"<<endl;

cin>>m;

int c=m;

double running_time[c];

while(c>0)

{

int arr[n];

int x;

for(x=0;x<n;x++)

{
arr[x] = rand();

}

clock_t start = clock();

int pos = biggest(arr,n);

clock_t t_end = clock();

c--;

running_time[c] = 1000.0*(t_end-start)/CLOCKS_PER_SEC;

}

double avg_running_time = calculate(running_time,m);

result.push_back(make_pair(n,avg_running_time));

cout<<"Enter 1 for iteration\nEnter 2 for exit\n";

cin>>choice;

}

for(int x=0;x<result.size();x++)

{

cout<<result[x].first<<" "<<result[x].second<<endl;

}

}