Why is this code giving time complexity of O(n) :
list< int > myList = { 2, 6, 12, 13, 15, 18, 20};
cout << binary_search(myList.begin(), myList.end(), 20) ;
Time Complexity Analysis
@vishwassingh499
Hello Vishawas,
here in above code we are given a list stl which is very similar to linked list.
and to find mid to apply b search we need to traverse half of the list every time thats why it is O(n)
recurrence relation will be
T(n)=T(n/2) + O(n) .// linear work to find mid
on solving this recurrence relation we get O(n)
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.