Question

2.) Consider an input array A of size n in which n − 1 of the...

2.) Consider an input array A of size n in which n − 1 of the elements have identical values and the remaining one value is smaller than the n − 1 identical values. What is the running time of Heapsort with input A?

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

2) The running time of Heapsort with input A will be O(n log n).

Heap sort requires two steps. One is creating the tree and the other one is heapify process. As we already know that, apart from one element other elements are identical to each other. So, the heapification process will run for that element and the complexity will be O(n log n). If all the elements in the array were identical then it will take O(n) times as no heapification will be required. In that case only traversing the tree will be required which will take O(n) time. But, since one element is smaller than all other equal elements, so we will require the heapification. So, it will take O(n log n) time.

Please comment in case of any doubt.
Please upvote if this helps.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1) Develop a C++ function that determines the average value of an array of type double...
1) Develop a C++ function that determines the average value of an array of type double elements double GetAverage(double array[], int size) The function should accept as input an array of double values The function should accept as input the number of elements in the array of double values The function should return a double value which is the array's average value 2) Develop a C++ function that determines the variance of an array of type double elements double GetVariance(double...
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of...
Find the worst-case complexity of the algorithm below. Show your work. UFSizeCalc Input:  uf: Union-Find array of size n Input: n: size of uf Output: size array for uf; that is, an array s such that s[r] equals the number of elements in the Union-Find tree rooted at r, for every root r (s may have any value for indexes that are not roots of uf) Pseudocode: For i = 1 to n uf.Find(i) size = Array(n) Initialize size to be...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
C++ program for : 1. Given an array of real numbers and the dimension n (n...
C++ program for : 1. Given an array of real numbers and the dimension n (n is entered from the keyboard). B form an array, each element bi - arithmetic mean of the array elements and excluding ai. 2. Given an array of integers dimension n. Change the array so that all the elements of the module which is not equal to the maximum element of the array, replaced by zero, and equal - unit. 3. Given an array of...
We are given an array A of size n containing n positive and negative integers (the...
We are given an array A of size n containing n positive and negative integers (the array is indexed starting from 0). Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n and Pk=j k=i A[k] is maximized. Input sequence: [2, -4, 1, 9, -6, 7, -3] Output: [1, 9, -6, 7] or i = 2 and j = 5 Input sequence: [1, 2, 3, 4, 5, 6, -3] Output: [1,...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Develop a program that will sort the elements of a single dimension array. Program Requirements: 1....
Develop a program that will sort the elements of a single dimension array. Program Requirements: 1. Declare a single dimension array of size n 2. Input n elements to a single dimension array 3. Sort the elements of an array from highest to lowest and vice versa Also, the program will identify and output the highest and lowest integer.
For questions 1 and 2 declare the array size as name constant first then use it...
For questions 1 and 2 declare the array size as name constant first then use it to declare the array 1. Declare an array named scores of type double and size 30. 2. Declare an array named names of string objects and size 15 3. Given the following array definition: int values[] = {2, 5, 8, 11}; What does each of the following display? cout << values[1];         B) cout << value[3]+values[0];   Define a three element array named letters, initialize it...
Consider the C code below which reverses the elements in the array A in place. Both...
Consider the C code below which reverses the elements in the array A in place. Both array indexing and pointer versions are given. Assume that A holds doubleword integers and that size is the number of elements in the array. Translate to RISC-V using as few instructions as possible. For your RISC-V code, assume the base address of A is initially in x10 and that the number of elements in the array (i.e., size) is initially in x11. long long...
In heapsort we view an array as a binary tree using the following mapping: a[0] is...
In heapsort we view an array as a binary tree using the following mapping: a[0] is the root of the entire tree and for element a[i], its left child is a[2i+1] and its right child is a[2i+2]. Answer the following questions for an array of size n. ( Answers in some cases may be in terms of n.) a) What is the index of the parent a[i] for any i > 0? b) What is the biggest index for which...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT