why is the time complexity linear?
In question 2 of quiz
Choose the correct output and time complexity for the following code : list< int > myList = { 2, 6, 12, 13, 15, 18, 20}; cout << binary_search(myList.begin(), myList.end(), 20) ;
we need to find time complexity?
@Ak07
Aryan,
here we are given list and list stl is very similar to the link list i.e we need to to traverse list from start to reach a particluar index.
if i represent recurrence relation for binary search on list then it will be something as ->
T(n)=T(n/2) + O(n) // O(n) because to reach to mid element we need to traverse half of the list which is equivalent to O(n) work.
On solving this recurrence relation we get O(n) time complexity
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.