PROBLEM: The procedures used in the basic run time analysis of algorithms shows

Question

PROBLEM:

The procedures used in the basic run time analysis of algorithms shows that loops frequently play a significant role in determining the big-O of the algorithms. Here are five (5) different loops (written in pseudo-c++) that do some summations and an output.

Loop 1:

   sum = 0;

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

     sum += i;

   cout << sum;

Loop 2:

   prod = 1;

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

      prod *= i;

   cout << prod;

Loop 3:

   prod = 1;

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

     prod *= i;

   cout << prod;

Loop 4:

   sum = 0;

   for (i = 1; i <= 2*n; i++)

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

       sum += i;

   cout << sum;

Loop 5:

    sum = 0;

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

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

          sum += i;

      cout << sum;

Set up and do an experimental analysis of these five loop forms. Compare the run times using both the ratio test and the power test to estimate the run times of the different loops.

Explanation / Answer

Loop 1:
time complexity = O(n)
output sum=(n*(n+1))/2
if n =5
than sum=1+2+3+4+5=15

Loop2:
time complexity = O(n)
output prod=2n!
if n = 5
than prod=1*2*3...10=3628800

Loop3:
time complexity = O(n^2)
output prod=(n*n)!
if n=5
than prod=2076180480

Loop4:
time complexity = O(n)
output sum= sum of ith row ith time from 1 to 2n
if n=5
than sum=385

Loop5:
time complexity = O(n^2)
output sum= sum of ith row ith time from 1 to n*n
if n=5
than sum=5525

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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