please give a detailed analysis of time complexity in code below

the code is of TSORT problem.
i am using the list container to store the elements of array in sorted manner by applying binary search(using upper bound function) on the elements already present in the list,for finding the position where to insert the next element.

[link text][1]

Solution is O(n^2). Note that std::upper_bound is linear if the iterator is non-random-access (which happens when you use std::list). Taking a look at the C++ reference:

The number of comparisons performed is logarithmic in the distance between first and last (At most log_{2}{(last - first)} + O(1) comparisons). However, for non-RandomAccessIterators, the number of iterator increments is linear.

It’s true that inserts in std::list are O(1), but for that you have a bad trade-off. Try using std::set instead, I believe it also has an upper bound method and O(log n) insert.

2 Likes

i think the upper bound function is taking logn time.please clarify it.

Even i ahve a serious question mark on what that code is trying to do. :confused:

1 Like

Refer this code
https://www.codechef.com/viewsolution/14685135