Pytanie o złożoność obliczeniową napisanych funkcji

Napisałem te dwie funkcje w Pythonie które szukają k-tej najmniejszej liczby w liście (mogą być duplikaty):

def find_ksmallest1(ar, k):
    ar.sort()
    return ar[k-1]

def find_ksmallest2(ar, k):
    af = ar[:]   
    for j in range(k):
        smallest = af[0]
        for i in af:
            if i < smallest:
                smallest = i
        af.remove(smallest)
        if j == k - 1:
            return smallest

Pierwsza ma złożoność obliczeniową jak ten sort, ale mam wątpliwości co do drugiej, czy jest to O(n) bo przechodzi k razy po całej liście a k to stała i można pominąć, czy moje rozumowanie jest błędne?

Kwadratowa będzie, masz pętlę w pętli, a, k, w najgorszym przypadku może być rozmiarem tablicy.

Jak chcesz O(n) to masz np. magiczne siodemki piatki.

https://pl.wikipedia.org/wiki/Algorytm_magicznych_pi%C4%85tek

Ale z praktycznego punktu widzenia O(nlogn) jest spoko.

randomize111 napisał(a):

Napisałem te dwie funkcje w Pythonie które szukają k-tej najmniejszej liczby w liście (mogą być duplikaty):

def find_ksmallest1(ar, k):
    ar.sort()
    return ar[k-1]

Pierwsza ma złożoność obliczeniową jak ten sort, ale mam wątpliwości co do drugiej, czy jest to O(n) bo przechodzi k razy po całej liście a k to stała i można pominąć, czy moje rozumowanie jest błędne?

Już nie mówiąc o tym, że złożoność .remove jest również liniowa.
A co do tego czy k jest stała i można pominąć czy nie - no to już zależy od czego chcesz uzależnić złożoność którą sobie liczysz. Być może chciałbyś to zrobić względem k, a n jest tylko jakimś parametrem, i wtedy wyjdzie ci O(f(k)) a nie O(f(n)).

Jak chcesz użyć wbudowanych struktur to heapem można w nlog(k).