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.