下面函数实现了从一个长度为n的数组中得到第K小的数，请分析它

下面函数实现了从一个长度为n的正整数数组中得到第K小的数（无解返回-1），请分析它的平均时间复杂度为（）

int partition(int arr[], int left, int right)
{
    int j = left, tmp;
    for (int i = left; i < right; ++i){
        if (arr[i] <= arr[right]){
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;

            j += 1;
        }
    }
    tmp = arr[j];
    arr[j] = arr[right];
    arr[right] = tmp;
    return j;
}

int find_kth(int arr[], int n, int K)
{
    int left = 0, right = n - 1;
    K -= 1;
    while (true){
        int pivot = partition(arr, left, right);
        if (pivot == K)
            return arr[pivot];
        if (pivot > K)
            right = pivot - 1;
        else
            left = pivot + 1;
    }
    return -1;
}