basically worst case will be O(n^{2}) when k=n

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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))); }

- Explain what the function computes.
- What is the worst-case complexity of this algorithm in terms of the length of the input sequence $A$?
- Give an example of a worst-case input for this algorithm.

+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.

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.

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)

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, 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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,515 questions

52,763 answers

183,377 comments

68,234 users