For question no 2 how is the complexity linear in terms of size of the list?

#1

We are using binary search. Shouldn’t it be logarithmic ?

#2

binary search algorithm for logarithmic time needs two conditions:

  1. elements should be sorted
  2. random access is available(arrays, vectors)

list in cpp refers to linked list, which is sequential access, you can not access mid element in O(1) time during binary search. so its time complexity is linear.

thanks

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.