Algorithm and Running Time Analysis: Give the tightest possible upper bound for

Question

Algorithm and Running Time Analysis: Give the tightest possible upper bound for the worst case running time for each of the following in terms of N. Assume that the most time-efficient implementation is used.

Popping a value in a stack implemented as linked list. Be specific in explaining how you get the runtime you provide. Explanation e. f Given a FIFO queue implemented as a linked list, find and remove all of the values greater than 10, leaving the rest of the queue in its original order. Explanation Given a FIFO queue implemented as a linked list currently containing N values, enqueue N more values so that when you are finished the queue will contain 2N values (Give the total time for goqueueing N more values). Explanation g. h. Finding something in a sorted array? Explanation i. Finding and removing all values greater than 12 from a stack implemented with a linkedlist (leaving the rest of the stack in its original order)? Explanation

Explanation / Answer

Popping a value in a stack implemented as linked list. Be specific in explaining how you get the runtime you provide.
Answer: O(1)
Explanation: Since Stack using Linked List, Top will, point to the top most element of Stack so popping will just take O(1) time


Given a FIFO queue implemented as a linked list, find and remove all of the values greater than 10, leaving the rest of the queue in its original order.
Answer: O(n)
Explanation: Since Queue using Linked List, We need to iterate whole Queue to find the element greater than 10 and keep on dequeing them , So overall it will take O(n) as we need to iterate Queue of n elements

Given a FIFO queue implemented as a linked list currently containing N values, enqueue N more values so that when you are finished the queue will contain 2N values (Give the total time for enqueueing N more values)
Answer: O(n)
Explanation: Queue takes O(1) time to add an element that is done in Rear pointer, SInce we need to add N elements it will take O(n) time

Finding something in a sorted array?
Answer: O(log n)
Explanation: Searching an element in Sorted array will take log n time using Binary Search

Finding and removing all values greater than 12 from a stack implemented with a linkedlist (leaving the rest of the stack in its original order)
Answer: O(n)
Explanation: Since stack using Linked List, We need to iterate whole stack to find the element greater than 12 and keep on Popping them , So overall it will take O(n) as we need to iterate Stack of n elements


Please RATE, If helpful

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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