6. (20 points) Letters for you to use to fill in the blanks a e(1) b (log n) c (

Question

6. (20 points) Letters for you to use to fill in the blanks a e(1) b (log n) c (n) d (nlogn) f linear search binary search For each statement below, fill in the blank with a letter chosen from the above list Correct responses may or may not be unique . As a function of its radius n, the area of a circles grows as . As a function of its diameter n, the area of a circle grows as » As a function of its number of nodes n, the height of a binary tree grows as » The MinHeap we implemented was of a fixed size. Imagine that we are going to allocate a new array in MinHeap to accommodate more elements when the existing array is full. Consider the total cost of inserting n items into such a heap whose size is initially 1, with array.length-2 When the array is full it is replaced by an array that is one cell larger than the old array. The cost of inserting n items using this strategy is When the array is full, it is replaced by an array that is twice the size of the old array. The cost of inserting n items using this strategy is » The time to perform 10 extractMin() operations in a heap initially of size n, where n 10, is . Given a heap of size n, the time to extract half of its elements is . Consider an array such that its elements are already sorted. To find a given element in O(n) time you can use or . Consider an existing linked list of n elements without a tail reference. If we add a tail reference to that implementation, the increase in required storage 1S

Explanation / Answer

If you post more than 4 parts in a single question, as per chegg guidelines I would have to answer only 4 parts.

1.

Area is a function of radius and varies with square of radius.

Also, radius is a function of 'n' (given).

So, Area grows as O(n^2).

Answer is (e) O(n^2).

2.

Area is a function of radius and varies with square of radius.

Diameter varies linearly with radius, as

                             diameter = 2 * radius

So, radius grows the same way as diameter gows. Also, radius is a function of 'n' (given).

So, Area grows as O(n^2).

Answer is (e) O(n^2).

4.

The extractMin() operation works by first extracting the minimum element and then calling the minHeapify() operation.

minHeapify() operation works in O(log n) .

Hence, 10 extractMin() would work in O(10 log n) = O(log n) time.

Answer is (b) O(log n)

5.

Extracting an element would take O(log n) time as explained in part 4.

Hence, extracting (n / 2) elements would take

                         O((n / 2) * log n) = O(n log n) time.

Answer is (d) O(n log n)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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