Binary search time complexity should be logn so correct output should be 4

#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.

#2

hello @sagar_aggarwal
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)

#3

dude we have not reached till there in the course so far :frowning: also in one question what does *max_element() function does?

#4

hello @sagar_aggarwal

reached where? havent u studied linked list?

this function just return maximum element of the array.

#5

No i am on Algorithmic STL in the course even before recurssion

#6

ok , then try this problem again after studying linked list

#7

How do i approch to solve this or understand that how compare functon is working
bool comp(string s1, string s2)
{
if(s1.length() < s2.length())
return 1;
else if(s1.length() > s2.length())
return 0;
else return s1 < s2;
}

vector< string > data = {“b”, “a”, “c”, “abc”, “bca”, “xy”};
sort(data.begin(), data.end(), comp);
for(string item : data)
cout << item << " ";

#8

u should know only one thing that is
if compare function returns true then swapping will not happen.
otherwise swapping will happen.

now just read the compare function and decide accordingly

1 Like
#9

why this is not going inside an infinite loop
string s = “bca”;

do {
cout << s << ’ ';
} while(next_permutation(s.begin(), s.end()));

cout << s;

#10

You are a Gem :slight_smile: :innocent:

#11

here next_permuation will return false , if no next greater permuation is possible. and while loop will break after that.

for example->
cba -> no greater string is possible .
so next perm will return false and loop will stop

#12

so s should have stored cba but outside loop when cout<<s; it is printing abc

#13

yeah … becuase if next largest permuation is not possible then it return smallest possible permuation which in our case is abc

#14

while( @aman212yadav !=smile)
{
cout<<“You made this course more worthful…Thank you”<<endl;

}

1 Like
#15

:sweat_smile::sweat_smile: . . . . . . . . . . . . . . . .

#16

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.