In the class
ShortestWindowSort() the method
sort(const vector<int>& arr) has its time complexity calculated to be
Ok, now let’s explain this in detail. There are several loops within the method
sort itself, 5 to be exact.
Let us calculate the time complexity of each loop. This turns out to be
O(N) for each.
Note that time complexity turned out to be
O(N) because we are looking at the worst possible cost.
Let us now sum up all these time complexities (of 5 loops). This yields us
5 * O(N). Since
5 is a constant, we will ignore it and are left with
O(N). Hence the time complexity of the method
sort turns out to be
Hope this solves the issue. Please feel free to reach out if there is any other issue.