educative.io

Proposed Solution is not really O(N)

Courses
,
#1

Array items can get looped multiple times, Big O notation tends to drop any constants, but I feel like in this case dropping them and not explaining why or how you got to the final conclusion of “O(N)” time complexity is detrimental to what people are trying to learn from this course.

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5612925563699200

#2

Hi @Nicolas_F!
In the class ShortestWindowSort() the method sort(const vector<int>& arr) has its time complexity calculated to be O(N).
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 O(N).
Hope this solves the issue. Please feel free to reach out if there is any other issue.

1 Like