273 views

Consider the following function that takes as input a sequence $A$ of integers with n elements,$A[1],A[2],….,A[n]$ and an integer $k$ and returns an integer value. The function length$(S)$ returns the length of the sequence $S$. Comments start with //.

function mystery(A, k){
n = length(A);
if (k > n) return A[n];
v = A[1];
AL = [ A[j] : 1 <= j <= n, A[j] < v ]; // AL has elements < v in A
Av = [ A[j] : 1 <= j <= n, A[j] == v ]; // Av has elements = v in A
AR = [ A[j] : 1 <= j <= n, A[j] > v ]; // AR has elements > v in A
if (length(AL) >= k) return mystery(AL,k);
if (length(AL) + length(Av) >= k) return v;
return mystery(AR, k - (length(AL) + length(Av)));
}
1. Explain what the function computes.
2. What is the worst-case complexity of this algorithm in terms of the length of the input sequence $A$?
3. Give an example of a worst-case input for this algorithm.
edited | 273 views

a. Function computes kth smallest element (if k<number of elements in the array, else it returns max element).
b. Time complexity = $O(k$*$n)$, where n is the number of elements in the array.
c. Worst case input: Array consists of a distinct increasing sequence of numbers and from this sequence, if we need to find nth smallest (i.e. max element) then it will take O$(n$*$n)$ time.
edited
+3

basically worst case will be O(n2) when k=n

0
please explain how you got O(kn) time complexity

is this argument correct?

since in an increasing order of sequence the number of comparison decrease by 1

eg. in an increasing sequence of n elements the no. of comparisons to find k'th order would be

n + (n-1) + (n-2) + ... + (n-k)

from which you removed the constant negative terms and got O(kn)
0

Recurrence Relation for this problem would be:T(n)=T(n-1)+O(n),T(1)=O(1),Since the partition on set of numbers could be in such a way that all the numbers(except v) are filtered out for the next iteration in any of (AL,AR) .Consider the set of numbers from 20 to 1 in decreasing order and if k=1,then we will have the worst case scenario.

0
When k>n , it will simply return the n th number of the the array, not the max element.
0

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.

+1 vote
1
+1 vote
2
+1 vote