The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

Consider the following function that takes as input a sequence $A$ of integers with n elements, $A$$\left [ A1 \right ]$, $\left [ A2 \right ], \ldots, \left [ An \right ]$and an integer $k$ and returns an integer value. The function length$(S)$ returns the length of 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.
asked in Algorithms by Boss (17.3k points)
edited by | 156 views

1 Answer

+2 votes
Best answer
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.
answered by Veteran (55.5k points)
edited by

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

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)

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. 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,686 questions
48,650 answers
63,961 users