Quiz- ALgorithms STL

#1

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) ;

  1. Output is 20 and time complexity is Linear in size of the list.

  2. Output is 1 and time complexity is Linear in size of the list.

  3. Output is 20 and time complexity is Logarithmic in size of the list.

  4. Output is 1 and time complexity is Logarithmic in size of the list.

The answer is option 2. But shouldn’t the TC be logarithmic?

#2

hello @arunimakhanna11
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