What is the time complexity for locating an element with a given value in a doub

Question

What is the time complexity for locating an element with a given value in a doubly-linked list of N elements sorted in ascending order?

(a) O(1) (b) O(log N) (c) O(N) (d) O(N log N)

What is the time complexity for popping off the first (i.e., oldest) element pushed onto a stack which contains N elements?

(a) O(1) (b) O(log N) (c) O(N) (d) O(N log N)

One way to reverse the sequence of elements in a queue would be to dequeue them and push them onto a stack one by one, then pop all the elements off the stack while enqueueing them again. What would be the time complexity of performing this sequence of operations with a queue of N elements?

(a) O(1) (b) O(log N) (c) O(N) (d) O(N log N)

Explanation / Answer

1)

c) O(N)

2)

it is the case for worst case scenario to pop up oldest element so you have to traverse and popping out all the element so time complexity is O(N)

Answer : O(N)

3)

we are going to see worst case

for deque operation it will take all the elemtent to dequeue so O(N) , for pusing them on to the stach take O(N)

popping out for worst case is O(N ) and for enqueue time complexity is O(N)

so total time complexity is = O(N) + O(N) + O(N) + O(N)

= 4O(N)

for larger N value it is O(N)

Answer = c) O(N)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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