1 Given a sorted input of size n Write time complexity (using notation) for each of the algorithms on the given input (a sorted input of size n) Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort Counting Sort Which of the algorithms has the best performance (best running time) Explain your answer 2 Given a reverse ordered input of size n Write time complexity (using notation) for each of the algorithms on the given input (a sorted input of size n) Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort Counting Sort Which of the algorithms has the best performance (best running time) Explain your answer 3 Given an input of n numbers The numbers are positive integers and bounded by 3n 2 (each input value is less or equal to 3n 2 ) Analyze time complexity of Counting Sort on the given input Explain your answer 4 Given an input of n numbers The numbers are written in decimal system using up to 3n digits Analyze time complexity of RadixSort on the given input Explain your answer 5 Given a reverse ordered input and search key K Modify the Sequential Search of a Sorted Array Algorithm such that it works on the given reverse ordered input of size n Write the pseudocode for it 6 Given a reverse ordered input and search key K Modify the Binary Search of a Sorted Array Algorithm such that it works on the given reverse ordered input of size n Write the pseudocode for it

The Answer is in the image, click to view ...

Question: 1. Given a sorted input of size n. Write time complexity (using notation) for each of the algorithms on the given input (a sorted input

1. Given a sorted input of size n. Write time complexity (using notation) for each of the algorithms on the given input (a sorted input of size n):

Insertion Sort

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

Counting Sort

Which of the algorithms has the best performance (best running time)? Explain your answer!

2. Given a reverse-ordered input of size n. Write time complexity (using notation) for each of the algorithms on the given input (a sorted input of size n):

Insertion Sort

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

Counting Sort

Which of the algorithms has the best performance (best running time)? Explain your answer

3. Given an input of n numbers. The numbers are positive integers and bounded by 3n² (each input value is less or equal to 3n²). Analyze time complexity of Counting Sort on the given input. Explain your answer!

4. Given an input of n numbers. The numbers are written in decimal system using up to 3n digits. Analyze time complexity of RadixSort on the given input. Explain your answer!

5. Given a reverse-ordered input and search key K. Modify the Sequential Search of a Sorted Array Algorithm such that it works on the given reverse-ordered input of size n. Write the pseudocode for it.

6. Given a reverse-ordered input and search key K. Modify the Binary Search of a Sorted Array Algorithm such that it works on the given reverse-ordered input of size n. Write the pseudocode for it.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Use JAVA: Problem 1: Given k sorted arrays of size n, design an algorithm merge these arrays into a single sorted array of size kn? (Hint: A sorted array is a min heap. If you have k min heaps, can...

JAVA Objective: Sorting Algorithms (first set) comprehension Here is the code for the first set of sorting algorithms we have seen: public int select(Comparable[] a, int k) { //find the location of...

1 ) Count nodes Given a binary tree root, a node X is named max node if in the path from root to X there are no nodes with a value greater than X . Return the number of max nodes in the binary tree....

Questions 1,2,3 are full programs. Can you solve them step-by-step please? Questions 7,10,11,12,13 are multiple choice. Need only a simple explanation! Question 1. ( 6 points) This question involves...

complete the quick sort and insertion sort functions only without modifying the rest of the java code: import java.util.concurrent.ThreadLocalRandom; class ProgrammingAssignment 1 { / / Function to...

complete the quick sort and insertion sort functions only without modifying the rest of the code: import java.util.concurrent.ThreadLocalRandom; class ProgrammingAssignment 1 { / / Function to swap...

his problem relates to insertion sort ( see pseudocode below ) . Use 1 n as data for input of size n . For example, n 1 2 3 n 2 n 1 is a specific input of size n . When I say analyze the algorithm ,...

Have a C compiler which is ANSI conforming in all respects except that it has no facility for the definition, declaration or use of standard C structures. Outline a set of routines written in this...

THIS IS THE QUESTION ABOUT THE D&L OF ALGORITHMS Design and Complexity Analysis QUESTION 1: give pseudocode for interpolation search, and analyze its worst-case complexity. Asymptotic Notation,...

1 12. Which of following statements is not true about a RB Tree? A) There are no consecutive red. B) Each physical leaf nodes in RB Tree has two virtual children nodes, T.nil. C) The root node in RB...

Calculate the components of a four-vector A and the scalar product of the four-vectors A^ and B^ where (a) A^ = (A^t , A^x , A^y , A^z ) and B^ = (B^t , B^x , B^y , B^z ) in Minkowski space defined...

The following table shows the net income and average total assets (in millions) for a recent fiscal year for RONA inc. and Canadian Tire Corporation, Limited: a. Compute the return on assets ratio...

Suppose you're offered a investment that will live W money in six years $ 1 0 , 0 0 0 to invest what is the implied rate of interest

Seved Help 14 Wisconsin Snowmobile Corp. is considering a switch to level production Cost efficiencies would occur under level production, and aftertax costs would decline by $31,500, but inventory...

4. Who should be invited to attend?

7. How will you encourage her to report back on the findings?

Were the decisions based on appropriate facts?