Binary_search inbuilt function

#1

the correct answer for the time complexity of binary search is given to be linear instead of log for 2nd Question, How is that correct?

#2

hello @D19APPPP0006
its time complexity will be O(n)

reason->
list stl is like linked list i.e we cannot ranomly access any element . if we want to access any element then we need to traverse from start of the list to reach that particular node.

Now because we are applying binary search on list.
getting mid element will be O(n) // o(n) because to get mid element we need to traverse half of the list .

so the recurrence relation for this problem will be
T(N)=T(N/2) + O(n)
on solving this relation u will get
T(n)=O(n)

1 Like
#3

thank you very much, i didn’t know that list worked like linked list.
i thought of it as array.

#4

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.