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

Question

6. (20 points) Letters for you to use to fill in the blanks: a 6(1) b (log n) c (n) d (nlogn) f linear search g 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 ·The worst-case time to insert n integers into an initially empty min heap is » Consider a queue implemented as a linked list without a tail reference. Suppose that queue is used for n enqueue operations followed by n dequeue operations The best implementation can do this in e Consider a stack implemented as a linked list without a tail reference. Suppose that stack is used for n push operations followed by n pop operations. The best implementation can do this in time. » The time to perform n extractMin() operations in a heap initially of size n is

Explanation / Answer

Answer:

1) theta(n) , because login wont effect much.

2) theta(n) , As there is an algo which can build a heap in theta n time.

3) theta(n^2) ,  In LL, for deleting each element, head pointer has to go to the end of LL as there is no tail pointer

So n^2.

4) theta(n) , stack n push pop can be done in Theta n time .For same reason as above

5) theta(nlogn) , to extract min takes n time and to repeat the process in n times is total theta(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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