Doubts on quiz of algorithm stl

#1

Q10
could not understand how abc is printed at the end…
Q9
how is the algo taking O(N) space??
Q7
which algorithm does the Cpp inbuilt sort function uses??
Q2
how is it taking linear time complexity to search using binary_search function under algorithm stl?

#2

Ques 2.
Actually ,in this question the binary search is implemented on linked list not in array or vector and binary search in list takes o(n) time while in vector or array it takes o(log n)
proof :-
To perform a Binary search based on Divide and Conquer Algorithm, determination of the middle element is important. Binary Search is usually fast and efficient for arrays because accessing the middle index between two given indices is easy and fast(Time Complexity O(1)). But memory allocation for the linked list is dynamic and non-contiguous, which makes finding the middle element difficult. we can find middle element of linked list using two pointer method which will take (N/2) operations where N is the length of range ({start,end})
so overall in worst case (i.e element not found)=(N/2+N/4+N/8+N/16…) == N
thus time complexity is O(N)

#3

Ques 7.
Cpp inbuilt function uses a special sorting algorithm known as Intro Sort
Intro sort is a hybrid sorting algorithm , that means it uses multiple sorting algorithms depending on the input , and its worst case time complexity is o(nlogn)

#4

Ques 9.
this algo is taking o(n) space because you are declaring a local variable res which is of same size as input string

Ques 10 .
for next_permutation :-
return value: true : if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangementis not greater than the previous, but the lowest possible (sorted in ascending order).

also, every time you call next_permutation(s.begin(),s.end()) it will change the string to next greater lexiographical order and if there is no next_greater permutation then it converts the string in ascending order

so , what happens here is,
bca is printed
then next_permutation is called and returns true (cab is possible)
cab is printed
then next_permutation is called and returns true (cba is possible)
cba is printed
then next_permutation is called and returns false (abc is lexiographically smaller than cba)

abc is printed from the cout statement outside the loop