This is C++ and must compile in visual studios. Run-Time Analysis Please impleme

Question

This is C++ and must compile in visual studios.

Run-Time Analysis

Please implement the following functions (Prefix Average 1 and Prefix Average 2). Give an analysis of the running time (Big-O) for several values for each function (on “paper”). Compare your analysis with the actual running time. (Use and clock() function using the example provided below.)

Prefix Averages (Quadratic): The following algorithm computes prefix averages in quadratic time by applying the definition.

Algorithm prefixAverages1(X, n)

      Input array X of n integers

      Output array A of prefix averages of X   

      A ¬ new array of n integers           

      for i ¬ 0 to n - 1 do                   

            s ¬ 0                 

            for j ¬ 0 to i do     

                  s ¬ s + X[j]          

            A[i] ¬ s / (i + 1)          

      return A                             

Prefix Averages (Linear): The following algorithm computes prefix averages in linear time by keeping a running time.

   Algorithm prefixAverages2(X, n)

      Input array X of n integers

      Output array A of prefix averages of X       

      A ¬ new array of n integers             

      s ¬ 0                                   

      for i ¬ 0 to n - 1 do                    

            s ¬ s + X[i]                      

                  A[i] ¬ s / (i + 1)                

      return A

Starter Code

Use the following code as a “starter”. The code includes a snippet of what your main function will look like to analyze the running times (using the sample “Ex1” function). You will need to implement the “prefixAverages1” and “prefixAverages2” functions.

//Run Time Analysis - Homework 1

#include     // needed to perform C++ I/O

#include

using namespace std;

void prefixAverages1(int[], int); //declaration of prefixAverages functions (to be implemented below main)

void prefixAverages2(int[], int);

double Ex1(int[], int); //Ex functions are example functions to show how to use "time" classes

double Ex2(int[], int);

double Ex3(int[], int);

double Ex4(int[], int);

int Ex5(int[], int[], int);

const int MAX = 100000;

int main ()

{

       cout<<"START running........"<

       clock_t start, stop;

       double res;

       int count;

       int A[MAX]={0};

       int B[MAX]={0};

       //initialize the array

       for(int i=0; i< MAX; i++)

       {

              A[i]= i+1;

              //cout <<" A[" <

       }

       cout <

    start = clock();

       res= Ex1(A, MAX);

       stop = clock();

       cout<<"The sum of the elelments in A is " <

       cout <<"Running time for Ex1 is " << static_cast(stop - start)/(CLOCKS_PER_SEC) <

       cout <

Explanation / Answer

vector<int> prefixAverages1(vector<int> x,int n)
{
   vector<int> a array(n);
   int sum;
   for(int i = 0; i < n ; i++){
       sum = 0;      
       for(int j = 0; j < i ; j++){
           s = s + x[i];
       }
       a[i] = s/(i+1);
   }
   return a;
}

vector<int> prefixAverages2(vector<int> x,int n)
{
   vector<int> a array(n);
   int sum = 0;
   for(int i = 0; i < n ; i++){      
           s = s + x[i];
           a[i] = s/(i+1);  
   }      
   return a;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.