1. Fill the blanks in the table with big Oh notation about the performance of th

Question

1. Fill the blanks in the table with big Oh notation about the performance of these operations

Operation Name

Performance (O(?))

Stack’s push(o) (array based)

Stack’s pop(o) (array based)

Queue’s enqueuer (array based)

Queue’s dequeuer (array based)

Vector’s InsertAtRank(r, o) (array based)

Vector’s InsertAtRank(r, o) (linked list based)

Vector’s ReplaceAtRank(r, o) (array based)

Vector’s ReplaceAtRank(r, o) (linked list based)

List’s ReplaceElement(p, o) (linked list based)

List’s SwapElements(p, q) (linked list based)

2. To include exactly 25 nodes, draw the tallest and shortest binary trees. What are the height of these two trees?

Operation Name

Performance (O(?))

Stack’s push(o) (array based)

Stack’s pop(o) (array based)

Queue’s enqueuer (array based)

Queue’s dequeuer (array based)

Vector’s InsertAtRank(r, o) (array based)

Vector’s InsertAtRank(r, o) (linked list based)

Vector’s ReplaceAtRank(r, o) (array based)

Vector’s ReplaceAtRank(r, o) (linked list based)

List’s ReplaceElement(p, o) (linked list based)

List’s SwapElements(p, q) (linked list based)

Explanation / Answer

Answer :

1.  Stack’s push(o) (array based) - O(1) , Each time another component is included toward the finish of array. Along these lines, independent of number of components as of now in the array, this task will dependably take same time. So it will be O(1).

2. Stack’s pop(o) (array based)-- O(n) Each time first component of array is expelled, all outstanding n-1 components are climbed. so it will be O(n).

For 3 and 4. Queue is a first in first out data structure. Similarly as with stack, getting to a particular component of the Queue should be possible in linear time O(n), as we have to cross it. However, we as a rule have a pointer/reference to the first and last component of the queue. In this way both enqueue and dequeue can be performed in consistent time O(1).

DEAR PLEASE DO RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

NOTE : KINDLY POST SEPARATELY AS WE ARE RESTRICTED TO ANSWER ONLY A SINGLE QUESTION FROM MULTIPLE POSTED QUESTIONS. FURTHERMORE , WE ARE ALLOWED TO ANSWER ONLY FIRST FOUR PARTS OF THE QUESTION WITH MANY SUB PARTS.

THANK YOU!!!

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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