When $K=n$, worst case time complexity will be $O(n^2)$ (example- array is sorted in decreasing order and we are looking for the smallest element (k=1) ,in that case $T(n)=T(n-1) +O(n) )$.If $k>n$ then time complexity is constant time $(O(1))$.
More Intuition on how worst case Time complexity can be $O(n^2)$:
Let mystry(A,K) is called where A has n elments.If A[1]>K th smallest number then, mystry(AL,K) will be called ,
if A[1]< k th smallest number then mystry(AR,K) will be called.
In both the above cases recursive sub problem size will be definitely less than the original problem( length(AL)< length(A) in first case and $length(AR)<length(A)$ in second case).If $A[1]$ is itself k th smallest number then no recursive subproblem will be called and we will get A[1] as answer.
In summary:
Case 1: $A[1]> K$ th smallest element
$T(n)= T(n-i) + O(n)$
Here $T(n-i)$ is the time to solve the recursive subproblem (mystry(AL,K)) and $O(n)$ is the time to generate AL,AV,AR. Now in this case time complexity will be maximum when i=1 ( such that $T(n)=T(n-1) + O(n))$
Do we have any input combination such that i equals to 1 in this case?
Yes, we have . For example if initial input is sorted in decreasing order with distinct numbers and K=1(looking for the smallest number) then, AL will have all the numbers except A[1] and mystry(AL,K) will be called, also further AL maintains the worst possible input combination(AL is sorted in decreasing order with distinct numbers) and this continues . So in Case 1 worst case time complexity can be $O(n^2) [T(n)=T(n-1) + O(n)$ leads to $O(n^2)$ time complexity]
Case 2: $A[1]< K$ th smallest element
$T(n)= T(n-i) + O(n)$
Here T(n-i) is the time to solve the recursive subproblem $(mystry(AR,K))$ and O(n) is the time to generate AL,AV,AR. Now in this case time complexity will be maximum when $i=1$ ( such that $T(n)=T(n-1) + O(n)$)
Do we have any input combination such that i equals to 1 in this case?
Yes, we have . For example if initial input is sorted in increasing order with distinct numbers and K=n(looking for the greatest number) then, AR will have all the numbers except $A[1]$ and $mystry(AR,K)$ will be called, also further AR maintains the worst possible input combination(AR is sorted in increasing order with distinct numbers) and this continues . So in Case 2 worst case time complexity can be $O(n^2) [T(n)=T(n-1) + O(n)$ leads to $O(n^2)$ time complexity]
Case 3: $A[1]=K$ th smallest element
Time complexity will be $O(n)$ in this case( No recursive function will be called.
Source: Comments below by Sourav