Ace Test series

Question

Someone help with this...I am getting option-b but key is opt-a

a)

b)

c)

d)

Comments

Can you explain how are you getting option B?

---

O(N+N+N^2) =O(N^2)

---

It is not right to consider Big-O for other operations because the question specifically mentions that we have to take theta for two of them. Since the question involves different notations so our answer should be precise.

Ο(N) is for all insert operations at front : that cannot take time more than N.

Θ(N) is for search operations for a specific value : that takes time roughly as fast as N.

Θ(N^2) is for delete operations from the end : that takes time roughly as fast as N^2.

Now if we combine these operations then the total tc will be the dominating term which is Θ(N^2).

If we want to search for a "specific" value in a single linked list then will it always take O(N)?. I hope you got the point.

---

Understood. Thank you :)

Answer 1

A