Analysis of Algorithms

/in /by

3. Analysis of Algorithms

Consider the following code for doing insertion sort

#include <iostream> #include <iomanip> #include <string> using namespace std; int count = 0; void insertionSort (int a[], int n) { int i, j, copy; count++; // for the initialization of i in the for loop for (i = 0; count++, i < n-1; count++, i++) { j = i+1; count++; copy = a[j]; count++; while (j > 0 && copy < a[j-1] ) { count++; // for the test to get into the body of the loop a[j] = a[j-1]; count++; j–; count++; } a[j] = copy; count++; } } void print(int a[], int n) { int i; cout << “sorted in ” << count << “steps: “; for (i = 0; i < n; i++) cout << a[i] << ‘ ‘; cout << endl; } int main () { int a[] = {34, 3343, 334, 644, 33, 31, 112, 119}; int n = sizeof(a) / sizeof(int); insertionSort (a,n); print (a,n); return 0; }

For the insertionSort subroutine only, do a full summation analysis similar to the one that is done for selection sort, given in the notes to determine the number of steps the sorting algorithm takes. You should end up with a formula in terms of n.

Now answer the following questions:

Save your time - order a paper!

Get your paper written from scratch within the tight deadline. Our service is a reliable solution to all your troubles. Place an order on any task and we will take care of it. You won’t have to worry about the quality and deadlines

Order Paper Now
  1. Plug the size of the the array into your formula and compute the number of steps the algorithm would be predicted to take. Compare this with the actual count printed by the algorithm.
    1. Are they the same?
    2. If not, why not?
  2. What would be the slowest time the algorithm can run (in terms of n)? What input would cause this slowest time.
  3. What would be the fastest time your algorithm could run (in terms of n)? For what input would this fastest time be achieved?

Computer Science homework help