Python algorithms and Big-O

Question

I am trying to wrap my head around time complexity when it comes to algorithm design using Python.

I've been tasked with writing a function that meets the following requirements:

Must be linear O(n) time
must return the nth smallest number from a list of random numbers

I have found the following example online:

def nsmallest(numbers, nth):
result = []
for i in range(nth):
    result.append(min(numbers))
    numbers.remove(min(numbers))
return result

As I understand it, Big-O is an approximation and only dominant part of the function is considered when analyzing it time complexity.

So my question is:

Does calling min() within the loop influence the time complexity or does the function remain O(n) because min() executes in O(n) time?

Also, would adding another loop (not nested) to further parse the resulting list for the specific number keep the algorithm in linear time even if it contains two or three more constant operations per loop?

If you have an O(n) operation in an O(n) loop, it will be O(n^2). As a side note: calling `min(numbers)` twice won't change the time complexity, but will make your code slower. — Thierry Lathuille, Jul 08 '21 at 11:05
Just a hint, you're looking for [Selection algorithm](https://en.wikipedia.org/wiki/Selection_algorithm). — Péter Leéh, Jul 08 '21 at 11:10
You can have a look at https://stackoverflow.com/questions/32928509/smallest-n-numbers-from-a-list — Thierry Lathuille, Jul 08 '21 at 11:12
His task is to write it, not to call the solution from a library, so heapq isn't really useful in my opinion.. — Péter Leéh, Jul 08 '21 at 11:14
Yes. I must write it out so heaps isn't an option. I will take a look at the selection algorithm you've suggested. Thank you! — Кафка, Jul 08 '21 at 11:17

score 2 · Answer 1 · answered Jul 08 '21 at 11:11

Does calling min() within the loop influence the time complexity or does the function remain O(n) because min() executes in O(n) time?

Yes it does. min() takes O(N) time to run and if you use it inside a loop that runs for O(N) time then the total time is now - O(N^2)

Also, would adding another loop (not nested) to further parse the resulting list for the specific number keep the algorithm in linear time even if it contains two or three more constant operations per loop?

Depends on what your loop does. Since you haven't mentioned what that loop does, it is difficult to guess.

curious.researcher · Accepted Answer · 2021-07-08T11:17:29.410

min() complexity is O(n) (linear search)
list.remove() remove is also O(n)
So, each loop is O(n).
You are using it k times (and k can be up to n), so result complexity would be O(n^2) (O(kn)).

The idea of worst case linear time algorithm that you are looking for is described here (for example).

kthSmallest(arr[0..n-1], k)

Divide arr[] into ⌈n/5⌉ groups where size of each group is 5 except possibly the last group which may have less than 5 elements.

Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array ‘median[]’ and store medians of all ⌈n/5⌉ groups in this median array. // Recursively call this method to find median of median[0..⌈n/5⌉-1]

medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

Partition arr[] around medOfMed and obtain its position. pos = partition(arr, n, medOfMed)

If pos == k return medOfMed 6) If pos > k return kthSmallest(arr[l..pos-1], k) 7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Thanks! I was a little confused by the method used to determine time complexity in the text book I'm using. This would be quadratic time then. Thanks for your guidance! — Кафка, Jul 08 '21 at 11:15

Python algorithms and Big-O

2 Answers2