Question

Problem 1 For each of the following three program fragments: A. Use big-O notation to analyze the running time (i.e. the value of sum). B. Implement the code in any programming language and give the actual running time for several values of N. o submit evidence you did this, i.e. the code you wrote C. Compare your analysis with the actual running times. o submit evidence you did this, i.e. tables or plots of data Fragment 1 sum = for i from 1 to n do sum = sum + 1 end Fragment 2 sum = 0 for i from 1 to n do for j from 1 to i do sum - sum + 1 end end Fragment 3 sum = 0 for i from 1 to n do for j from 1 to i^2 do for k from 1 toj do sum = sum + 1 end end end

Answer 1

The following three program fragments is

A. Fragment 1: O(n)

Fragment 2: O(n^2)

Fragment 3: O(n^3)

B. C++ implementation:

Fragment 1:

#include <iostream>

using namespace std;

 

// Function to calculate sum

// of number from 1 to n

int sum(int n)

{

   int sum = 0;

   for (int i = 1; i <= n; i++)

       sum += 1;

   return sum;

}

 

// Driver Code

int main()

{

   int n;

   cout << "Enter a number: ";

   cin >> n;

   cout << "Sum of numbers from 1 to " << n << " is " << sum(n);

   return 0;

}

Fragment 2:

#include <iostream>

using namespace std;

 

// Function to calculate sum

// of number from 1 to n

int sum(int n)

{

   int sum = 0;

   for (int i = 1; i <= n; i++)

   {

       for (int j = 1; j <= i; j++)

       {

           sum += 1;

       }

   }

   return sum;

}

 

// Driver Code

int main()

{

   int n;

   cout << "Enter a number: ";

   cin >> n;

   cout << "Sum of numbers from 1 to " << n << " is " << sum(n);

   return 0;

}

Fragment 3:

#include <iostream>

using namespace std;

 

// Function to calculate sum

// of number from 1 to n

int sum(int n)

{

   int sum = 0;

   for (int i = 1; i <= n; i++)

   {

       for (int j = 1; j <= i*i; j++)

       {

           for (int k = 1; k <= j; k++)

           {

               sum += 1;

           }

       }

   }

   return sum;

}

 

// Driver Code

int main()

{

   int n;

   cout << "Enter a number: ";

   cin >> n;

   cout << "Sum of numbers from 1 to " << n << " is " << sum(n);

   return 0;

}

C. Actual running times:

Fragment 1:

N   |  Running Time

------------------

1   |  1

2   |  2

3   |  3

4   |  4

5   |  5

Fragment 2:

N   |  Running Time

------------------

1   |  1

2   |  3

3   |  6

4   |  10

5   |  15

Fragment 3:

N   |  Running Time

------------------

1   |  1

2   |  5

3   |  14

4   |  30

5   |  55

What is program?

Programming is  involves writing code in a variety of languages, such as C++, Java, and Python, which are then compiled into executable instructions that the computer can understand and execute. Programming is used to create software applications and websites, as well as to automate tasks, control machines, and process data. Programming is an essential part of modern life and is used in many different industries, from business to science and engineering.

To learn more about program

https://brainly.com/question/26134656

#SPJ4