Use the (theta) notation to write down the worst-case time complexity for insert

Question

Use the (theta) notation to write down the worst-case time complexity for inserting an elemetn into a max-heap with n elements.

1, (4 pts) Use the notation to write down the worst-case time complexity for inserting an element into a max-heap with n elements. Solution: (log n). Grading: Binary. 2. (4 pts) Use the notation to write down the worst-case time complexity for finding the smallest element in a max-heap with n elements. Solution: (n). Grading: Binary. 3. (6 pts) The array representation ofa Ail 9 7 8 4 3 6 5 1 2 Show the binary max-heap obtained after the maximum element is deleted from the given max-heap (by applying the Extract-Max operation). You need to write the array content in the following table (tree view will NOT be graded). 1 2 3 457 8 A 8 7 6 4 3 2 5 1 Grading: Binary 4. (6 pts) The array reprcsentation of a max-heap is given in the following. 1 2 3 4 5 6 7 8 9 Al 9 78 4 3 6 5 1 2 Show the binary max-heap obtained after the value of Al8] is increased to 8 (by apply ing the Increase Key(A, 8, 8) operation). You need to write the array content in the following table (tree view will NOT be graded). i 1 2 3 45 6 7 8 9 A[i] |! 9 | 8 | 8 | 7 | 3 | 6 | 5 | 4 | 2 Grading: Binary

Explanation / Answer

To add an element to a heap we must perform the following operation :
a) Add the element to the bottom level of the heap.
b) Compare the added element with its parent; if they are in the correct order, stop.
c) If not, swap the element with its parent and return to the previous step.

The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n).
log n time to search for the correct place and log n time to swap.
O(log n) is the complexity.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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