Consider the program. What does the outputted value signify? By timing or counti

Question

Consider the program.

What does the outputted value signify? By timing or counting steps using several different inputs, conjecture the complexity of this algorithm. Can you prove your answer? Would your answer change if the value of 3 in the two commented lines changed to 6 or 9?

#includekios tream. h #include math.h #include iomanip.h double fcn (double x, double a) return (x+a/x) /2; int main() double epsilon le-3 3-digit precision double a, b-1; cout. setf (ios fixed) cout. setf (ios show point) 3-digit precision cout precision (3); cout Input number cin a while (fabs (fcn(b,a)-b) epsilon) b fcn (b,a); cout. b end return 0;

Explanation / Answer

The outputted value signify the program is calculating the square root of a number.

The complexity of this algorith is n. Since the while loop executes n time.

The precision does not have effect on the time complexity.

------------------------- run this modeified code for complexity check-----------------------

#include<iostream>
#include<math.h>
#include<time.h>
#include<iomanip>
using namespace std;
double fcn(double x, double a)
{
   return (x+a/x)/2;
}
int main()
{
long long   int N[]={10,20,40,100,200,400,1000,2000,4000,100000000000000000};
   double time_spent;
   for(int l=0;l<10;l++){
       clock_t begin = clock();
   double epsilon =1e-6;
   double a, b=1;
   cout.setf(ios::fixed);
   cout.setf(ios::showpoint);
   cout.precision(9);
   //cout<<"Input number";
//   cin>>a;
   while(fabs(fcn(b,N[l])-b)>epsilon)
   b=fcn(b,N[l]);
  
   cout<<b<<endl;
   clock_t end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
cout<<time_spent<<endl;
}
   return 0;
  
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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