What is the best-case runtime for inserting a new element into a minheap? Select

Question

What is the best-case runtime for inserting a new element into a minheap? Select all that apply.

Again, assume we use the array representation of heaps

a) O(n), where n is the number of nodes in the heap

b) O(n), where n is the value being inserted into the heap

c) O(n log n), where n is the number of nodes in the heap

d) O(n log n), where n is the value being inserted into the heap

e) O(1), because the heap might be empty

f) O(1), because the value being inserted might be very large, and therefore it would not percolate up

g) O(1), because the value being inserted might be very small, and therefore it would not percolate up

h) O(1), because the value being inserted might be very large, and therefore it would not percolate down

i) O(1), because the value being inserted might be very small, and therefore it would not percolate down

j) O(1), because we can only add values that are smaller than the root; if we try to add a value that is larger than the root, the process terminates immediately

k) There's no such thing as "best-case runtime."

Explanation / Answer

As per my knowledge, an element is added at the last index. If it is very large, it will take O(1), if it is smallest, it will take O(log n) to climb up the heap. therefore

option e is correct

option f is correct as large value will not climb up

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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