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)

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,782 questions

46,784 answers

140,766 comments

58,702 users