An array -S- contain n distinct elements- Consider a functionfi which is defined as-fi-max a-b-c-a-b-c- S and a b cWhat is the worst case time complexity to find set of all possible elements which are returned by function fiwhen array -S- is passed as an argument-

(a) If we observe their are ^nC_3 sets of 3 element possible. Out of nbsp; n elements only 2 samellest element cannot be present in " max element set ". So we ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Byju's Answer

Standard XII

Mathematics

Number of Functions Possible from Set A to Set B

An array 'S' ...

Question

An array 'S' contain n distinct elements. Consider a function $f_{i}$ which is defined as:

$f_{i} = {max (a, b, c) | \forall_{a, b, c} \in S a n d a \neq b \neq c}$

What is the worst case time complexity to find set of all possible elements which are returned by function $f_{i}$
when array 'S' is passed as an argument?

$O (n^{2})$

No worries! We‘ve got your back. Try BYJU‘S free classes today!

$O (n^{3})$

No worries! We‘ve got your back. Try BYJU‘S free classes today!

O(n)

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

O(n logn)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is C O(n)
(a)
If we observe their are $^{n} C_{3}$ sets of 3-element possible. Out of n-elements only 2-samellest element cannot be present in " max-element set ". So we can use 2-pass of selection sort to find 2-smallest elements, other than these two elements all will be present in "max-element set". So it will take
O(n) time.

Suggest Corrections

Similar questions

Q. You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

A, B, C

and

D

are the sets with

3, 3, 4

and

4

elements respectively. If

f (x)

is a function defined from

A

C

g (x)

is a function defined from

D

A

h (x)

is a function defined from

C

D

i (x)

is a function defined from

A

B

Then number of functions possible for

\begin{matrix} List I & List II (1) & h (x) if it is one - one & (P) & 36 (2) & g (x) if it is onto & (Q) & 40 (3) & i (x) if it is into & (R) & 64 (4) & f (x) if it is many - one & (S) & 48 (T) & 3 (U) & 24 \end{matrix}

Which of the following is the correct combination?

Q. Consider the following values of IE(ev) for elements W and X:-

\begin{matrix} E l e m e n t & I E_{1} & I E_{2} & I E_{3} & I E_{4} W & 10.5 & 15.5 & 24.9 & 79.8 X & 8 & 14.8 & 78.9 & 105.8 \end{matrix}

Other two elements Y and Z have outer electronic configuration

n s^{2} n p^{4}

and

n s^{2} n p^{5}

respectively.
According to given information which of the following compound (s) is/are not possible.

(A) W_{2} Y_{3} (B) X_{2} Y_{3} (C) W Z_{2} (D) X Z_{2}

Q. Consider that

n (S)

represented the number of elements in set S. If

n (A \cup B \cup C) = 40, n (A \cap B^{'} \cap C^{'}) = 5, n (B \cap A^{'} \cap C^{'}) = 10, n (C \cap B^{'} \cap A^{'}) = 6

then number of element which belongs to at least two of the set is

Q. An

n \times n

array V is defined as follow v[i,j] = i - j for all i, j, 1

\leq

i, j

\leq

n then the sum of the elements of the array V is

Join BYJU'S Learning Program

An array 'S' contain n distinct elements. Consider a functionfi which is defined as: fi={max(a,b,c)|∀a,b,c∈Sanda≠b≠c} What is the worst case time complexity to find set of all possible elements which are returned by function fi when array 'S' is passed as an argument?