What would be the slowest time the algorithm can run

Assignment Help Data Structure & Algorithms
Reference no: EM13762533

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:

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.

Are they the same?

If not, why not?

What would be the slowest time the algorithm can run (in terms of n)? What input would cause this slowest time.

What would be the fastest time your algorithm could run (in terms of n)? For what input would this fastest time be achieved?

Reference no: EM13762533

Write program for computing of shortest trajectories in abg

Write a program for computation of the shortest trajectories in ABG. Set X (a 2D table with or without obstacles), an element p for which the trajectories should be calculated

Declare linked list that will hold the elements in the stack

Create a new class named GenericStack that specifies a type variable that provides for generics. Declare a linked list that will hold the elements in the stack. Then, us

Question about isdn

Today ISDN cost $40 every month for BRI service which includes 1 D Channel and 2 B Channels. Every channel is capable of transmitting 64kbps of voice, data, video or fax for a

Principles and theory of security management

think of some intrusions - the disgruntled mailman flying onto the Capitol lawn on his gyrocopter and remember the couple who crashed a White House function a few years ago?

Is there a feasible solution for the problem

he running time of A on an input of size n is e(n log n). Given an input x of size n, give an algorithm that runs in time 0(n log2 n) and finds the cost of an optimal soluti

Write true if the statement is true or false

It is impossible to over-train a multi-layer feed-forward network using the back-propagation learning algorithm. It is guaranteed that the longer you train your system, the

Algorithm to compute binomial coefficients

Analyze the time taken by this algorithm under the unreasonable assumption that the addition C(n-1, k-1) + C(n - 1, k) can be carried out in constant time once both C(n-1, k

Discuss when you think a hash table should be used

Discuss when you think a hash table should be used and when you think it should it be avoided. Reply to others with support for or arguments against the use of hash tables in

Reviews

Write a Review

 
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd