i) Everybody in the class is prepared for the exam This is grammatically correct statement
ii). Babu invited Danish to his home because he enjoys playing chess.
This statement is ambiguous as there is no guarantee that Danish knows playing chess.

The Ratio of boys to girls is 7:3
Number of boys = 7x
Number of girls = 3x
Total number of students = 10x
So the possible value should multiple by 10.
Answer is 50.

The given statement is to fill the relationship of the subject and the action done by the subject.
Doctor is to surgery as writer is to book.

Explanation :
There are 5 bags having identical sets of 10 distinct chocolates. one chocolate is drawn from each bag, probability to find at least 2 chocolate is identical
The total number of such selections possible = 10*10*10*10*10 = 10^5.
We need to select such that at least two of them are identical.
We can count the number of ways with no chocolate being repeated and subtract it from total possible ways to get the required probability.
The number of ways to select all different/distinct = 10*9*8*7*6
Required number of selections= 10^5-10*9*8*7*6 = 69760
Required probability = 69760/10^5 = 0.69760

The problems mentioned are poverty and income inequality. But AOMs are not addressing the main problems directly. But it is a kind of generic step taken to address obesity. So AOMs are only addressing the obesity problem superficially but not addressing the real problems.

Array Z consists of 10 elements and that element's values are 1.
n=10,x=2
Initial total value is 1 => total=1.
For loop will execute 9 times.
loopindex=1, 1<=9 condition is true then
total = x * total + Y[loopIndex]= 2*1+Y[1]=2+1=3
loopindex=2, 2<=9 condition is true then
total=2*3+Y[2]=6+1=7
loopindex=3, 3<=9 condition is true then
total=2*7+Y[3]=14+1 =15
loopindex=4, 4<=9 condition is true then
total= 2*15+Y[4]=30+1=31
loopindex=5, 5<=9 condition is true then
total=2*31+Y[5]=62+1=63
loopindex=6, 6<=9 condition is true then
total=2*63+Y[6]=126+1=127
loopindex=7, 7<=9 condition is true then
Total =2*127+Y[7]=254+1=255
loopindex=8, 8<=9 condition is true then
total=2*255+Y[8]=510+1=511
loopindex=9, 9<=9 condition is true then
total=2*511+Y[9]=1022+1=1023
loopindex=10, 10<=9 condition is false then
Total value is returned which is 1023.
You can also write generalized formulae 210-1=1023

The given relational algebra expression will result in employees whose age is not minimum. The given conditional join, joins the relations if the age is greater than any of the ages mentioned in the database.

1. True
   Since broken connections can only be detected by sending data, the receiving side will wait forever. This scenario is called a “half-open connection” because one side realizes the connection was lost but the other side believes it is still active.
2. True
   The situation resolves itself when client tries to send data to server over the dead connection, and server replies with an RST packet (not FIN).
3. True
   Yes, a TCP Server can listen to the same port number even after reboot.  For example, the SMTP service application usually listens on TCP port 25 for incoming requests. So, even after reboot the port 25 is assigned to SMTP.
4. False
   The situation resolves itself when client tries to send data to server over the dead connection, and server replies with an RST packet (not FIN), causing client to finally to close the connection forcibly.
   FIN is used to close TCP connections gracefully in each direction (normal close of connection), while TCP RST is used in a scenario where TCP connections cannot recover from errors and the connection needs to reset forcibly.
   

The key insertions 10, 9, 6, 7, 5, 13 would result in the state of the given hash table.

The keys are inserted into the main hash table based on their 2 least significant bits.
→ The keys 5, 9, 13 will be inserted in the table with entry “01”.
→ The keys 6 and 10 will be inserted in the table with entry “10”
→ The keys 7 will be inserted in the table with entry “11”

→ Now the entry index 01 has collisions. Check the 3rd least significant bit of the keys 9,5,13. The 3rd least significant bit of the key is 0. Hence, key “9” placed as the left child of “01”. There will be collisions again in between the keys 5 and 13 which need to splitted.
Now check the 4th least significant bit of keys 5 and 13. The key 5 is placed as a left child because the 4th least significant is “0” and the key “13” is placed as right child because its 4th least significant is 1.
→ Now the entry index 10 has a collision. Check the 3rd least significant bit of the keys 10 and 6. The 3rd last significant bit of the key is 0. Hence, “10” is placed as the left child of index “10”.
The 3rd least significant value of “6” is 1. So, we are placed as the right child of index ”10”.

A tautology is a formula which is "always true" . That is, it is true for every assignment of truth values to its simple components.

Method 1:
S1: (~p ^ (p Vq)) →q
The implication is false only for T->F condition.
Let's consider q as false, then
(~p ^ (p Vq)) will be (~p ^ (p VF)) = (~p ^ (p)) =F.
It is always F->F which is true for implication. So there are no cases that return false, thus its always True i.e. its Tautology. 

 

S2: 

q->(~p (p Vq)) 

The false case for implication occurs at T->F case.
Let q=T then (~p (p Vq))  = (~p (p VT))= ~p. (It can be false for p=T).
So there is a case which yields T->F = F. Thus its not Valid or Not a Tautology.

Method 2:

push(54) ⇒ 54

push(52)=> 54, 52(top)

pop() ⇒ 54 (top)

push(55)==> 54, 55(top)

push(62) ⇒ 54,55,62(top)

s=pop() ⇒ 62 will store into the variable s then s=62

 

enqueue(21) ⇒     (front) 21(rear)

enqueue(24) ⇒   (Front)21, 24(rear)

dequeue()==> (front) 24(rear)

enqueue(28) ===> (front) 24,28 (rear)

enqueue(32)====>(front) 24,28,32 (rear)

q=dequeue() ⇒ value 24 will store into the variable “q”

q=24

 

S+q =62+24 =86

Sign bit S= 1. The given number is a negative number. 

Biased Exponent E = 2⁷ + 1= 129 

Actual Exponent e = E-127 

= 129- 127

= 2

The decimal value= (-1)^s x 1.M x 2^e 

= (-1) 1 x 1.1111 x 2² 

= - (111.11) 

= - (7 + 0.75) 

= -7.7

On converting (210)3 in decimal, we will get:=>

 2*3²+1*3=2*9+3=21₁₀ 

=>(15)₁₆

Bayes theorem:
Probability of event A happening given that event B has already happened is
P(A/B) = P(B/A)*P(A)  / P(B)

Here, it is asked that P( H transmitted / H received).

S can send signal  to H with 0.1 probability, S can send signal to L with 0.9 probability.
The complete diagram can be

Probability that H Transmitted (H_t) given that H received (H_r)is

P( H_t  / H_r) = P( H_r/ H_t) * P(H_t)  / P(H_r)

P(H-r) = probability that H received  = P( H received from H)+ P(H received from L)
It can be observed from the graph that H can receive in two ways (S to H to H) and (S to L to H)
The P(H_r) = 0.1*0.3 + 0.9*0.8= 0.03+0.72 = 0.75

P(H_received given that H_transmitted) =0.3
P(H transmitted ) = 0.1  i.e.

P( H_t  / H_r) = P( H_r/ H_t) * P(H_t)  / P(H_r)
                        = 0.3*0.1 / 0.75 = 0.04

 

v - e + f = 2

v is number of vertices

e is number of edges

f is number of faces including bounded and unbounded

8-e+5=2

=> 13-2 =e

The number of edges  are =11

The asymptotic notation order should be 

Constant < logarithmic < linear < polynomial < exponential < factorial 

F2 and F3 → Polynomial 

F1 → Exponential

By the order of asymptotic notations F1 is definitely larger. 

Method-1: 

Consider n=100

F1 : 100 ^100 ⇒ 1.e+200

F2 : N^log(100) base 2 ⇒  100 ^ log(100) base 2 ⇒ 100^6.6438561897747 = 1,93,96,00,91,15,564.181300016469223466

F3 : N^Sqrt(n) ====> 100^Sqrt(100) ⇒ 100^10 ⇒ 10,00,00,00,00,00,00,00,00,000

Method-2:

We can apply "log" on both sides. 

log(F1)=nlog10 (base 2)

log(F2)=(logn)^2 = logn * logn (base 2)

log(F3)=sqrt(n)logn (base 2) 

Answer: F2< F3< F1

Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1)  but not SLR(1).  So S1 is true.

Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n³) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true

Given functional dependencies set:

PQ->X

P->YX

Q->Y

Y->ZW

• While merging the tables there should be some common attribute(s) and it should be a candidate key of one of the tables.

• R1 should be merged with R2 because PT is a key of R2.
• R3 should be merged with PQSTX because Q is a key of R3.
• R4 should be merged with PQSTXY because Y is a key of R4.

• R1 should be merged with R3 because Q is a key of R3.
• R4 should be merged with PQSY because Y is a key of R4.
• Now, there is no common attribute in between R2(TX) and PQSYZW.
• Hence, D2 is lossy decomposition.

Variance(X) = Var[X]= E((X-E(X))^2)
For a dataset with single values, we have variance 0. EX-E(X)Y-E(Y)2>Var[X] Var[Y]
This leads to inequance of 0>0 which is incorrect.

Its not |x-E(x)|. Thus S2 is also incorrect.

The rod length of R7 is 18.

There are 3 different possible ways to get the maximum amount.
P[6] + P[1] → 17+1 = 18
P[2] + P[2] + P[3] → 5+5+8 = 18
P[7] → 18 = 18

Statement-1: FALSE: Root of T can never be an articulation point in G.
Statement-2:
Example-1:
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.




Here 2 and 6 are articulation points. If you consider node-1 ancestor and node-3 descendent, then without passing through from node -2, there exists a path from one node to another node.
Path from node-1 to node-3 If you consider node-5 ancestor and node-4 descendent, then without passing through from node-6, there exists a path from one node to another node.
Path from node-4 to node-5
The given statement is not TRUE for all cases. So, the given statement is FALSE.
Statement-3: FALSE: Leafs of a DFS-tree are never articulation points.
Statement-4: TRUE: The root of a DFS-tree is an articulation point if and only if it has at least two children.


Node 2 is an AP because any node from the first subtree (1, 2) is connected to any node from the second subtree (4, 5, 6, 7, 8) by a path that includes node 2. If node 2 is removed, the 2 subtrees are disconnected.

1. False, Large page size may lead to higher internal fragmentation.
2. False, To support pages of different sizes, the Instruction set architecture should support it. Multi-level paging is not necessary.
3. True, The page table has to be stored in main memory, which is an overhead. 
4. True, Paging avoids the external fragmentation. 

Minimum average waiting time amongst non-preemptive scheduling is given by SJF. So, avg waiting time = (0+10+26)/3 = 12 ms.

Register R1 will get value 10 from location 5000. So the loop in the given program will run for 10 times as the loop condition is based on ‘Dec R1’. When R1 is 0 then the loop terminates.

 

In these 10 iterations of the loop contents of memory locations 3000 to 3009 are changed as initial value of R3 is 3000 and in each iteration we update M[R3] ← R2 and the value of R3 is incremented to the next location 3001, 3002 etc.

 

But the value in location 3010 is unchanged and it will be the same as the initial value which is 50.

Tt(packet) = L / B.W => 2000 bits / 10^6 bps = 2  x 10^-3 sec = 2 millisec

Tt(Ack) = L / B.W. => 10 bits / 10^6 bps = 10^-5 sec = 10^-2 millisec = 0.01 millisec

Tp = 100 millisec

Total time = Tt(packet) + 2 x Tp + Tt(Ack)

=> 2 + 2 x 100 + 0.01 = 202.01 millisec

Efficiency = 50 % = ½

Efficiency = Useful Time /  Total time

½ = n x Tt / Total time 

 

=> 2 x n x Tt =  Total time

=>2 x n x 2 = 202.01  

=> n = 202.01 / 4 => 50.50

 

For minimum, we have to take ceil, Hence size of window = 51

L1 is decidable. 

We can take all strings of length zero to length 2021.

If TM takes more than 2021 steps on above inputs then definitely it will take more than 2021 steps on all input greater than length 2021.

If TM takes less than 2021 steps:

In such a case suppose TM  takes less than 2021 steps (let's say  2020 steps ) for string length 2021, 2022, 2023, then definitely TM  will take 2020 steps for all input greater than 2023. Hence in both cases it is decidable.

 

Similarly L2 is also decidable. If we can decide for all inputs then we can decide for some inputs also.

The given statements are true, they are well known facts.

1. The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
2. The sequence of returns corresponds to a postorder traversal of the activation tree.

If ‘G’ is a group with sides 6, its subgroups can have orders 1, 2, 3, 6.

(The subgroup order must divide the order of the group)

Given ‘H’ can be 1 to 6, but 4, 5 cannot divide ‘6’.  

Then ‘H’ is not a subgroup. 

G can be cyclic only if it is abelian. Thus G may or may not be cyclic.
The H can be cyclic only for the divisors of 6 and H cannot be cyclic for any non divisors of 6.

Theorem: A relation R on a set A  is an equivalence relation if and only if it is reflexive and circular.

 

For symmetry, assume that x, y ∈ A so that xRy, lets check for  yRx. 

Since R is reflexive and y ∈ A, we know that yRy. Since R is circular and xRy and yRy, we know that yRx. Thus R is symmetric. 

 

For transitivity, assume that x, y, z ∈ A so that xRy and yRz. Check for  xRz. Since R is circular and xRy and yRz, we know that zRx. Since we already proved that R is symmetric, zRx implies that xRz. Thus R is transitive.

XY’+Z’ is a minimal SoP expression which represents the function (X,Y,Z).

The expression XY’ + YZ’ + X’Y’Z’ can be reduced to XY’+Z’

XY’ + YZ’ + X’Y’Z

= Y’(X+X’Z’) + YZ

= Y’(X+Z’) + Y

= XY’ + Y’Z’ + YZ’

= XY’ + (Y’+Y)Z’

= XY’ + Z’.

The expression (X+Z’)(Y’+Z’) is a PoS expression which also represents the same function (X,Y,Z).

This SDT will never lead to infinite loop so option 2 is false. This SDT is type checking for bool as well as integer variables, hence this SDT can be used to correctly type-check any syntactically correct program involving boolean and integer variables.

Suppose a database system crashes again while recovering it from the previous crash then also we need to make use of the redo and undo list to recover the system.

• A sleep system call takes a time value as a parameter, specifying the minimum amount of time that the process is to sleep before resuming execution. The parameter typically specifies seconds, although some operating systems provide finer resolution, such as milliseconds or microseconds.

• strlen() is not system call.
• The function call malloc() is a library function call that further uses the brk() or sbrk() system call for memory allocation
• Exit also system call

ARP request is Broadcasting. ARP reply is unicasting.

count =0

S=5

func()

{

    wait();

    wait();

       count++;

       signal();

       signal();

}

Answer:

(1) Deadlock is possible.

For a deadlock free operation

No. of resources >= No. of process (Req-1) + 1

Here, no. of resources = 5 (semaphore value)

Each thread requires = 2 resources (wait call)

No. of threads = 5

      5 ≥ 5* (2-1)+1

         ≱ 6. So deadlock is possible.

This occurs when all 5 threads get blocked on first wait().

(2) count =5 is possible

When all threads enter CS and execute count++ sequentially.

(3) Count=1 is possible.

Assembly level:

     read R0, count

     inc R0, 1

     write count, R0

Thread - 1 reads Count=0 in R0, preempted

Thread-2 reads count=0, is r1, completes, count=1

Thread-3, 4 & 5 completes.

Thread-1 is given CPU

MC R0, 1, so R0=1

Write R0 to count.

So, Count=1. 

Option A accepts string “01111” which does not end with 011 hence wrong.

Option C accepts string “0111” which does not end with 011 hence wrong.

Option D accepts string “0110” which does not end with 011 hence wrong.

Option B is correct.

 

The NFA for language in which all strings ends with “011”

">

In a pipeline with k-stages, number of cycles to execute n instructions = (k+n-1) cycles

Here k = 5, n = 100

So we need a total of 5+100-1 = 104 cycles.

Clock cycle time = maximum of all stage delays + register delay

                           = max(150, 120, 150, 160, 140) + 5 = 160+5 = 165 ns

 

Time in ns = 104*165 = 17160ns

Given that the main memory is 2^32 bytes. So the physical address is 32 bits long.

 

Since it is a direct mapped cache the physical address is divided into  fields as (TAG, LINE, OFFSET).

 

Cache size is 32KB = 2^15 Bytes. 

Block size is 64 bytes = 2^6 bytes, so OFFSET needs 6 bits.

 

Number of blocks in the cache = 2^15//2^6 = 2^9, So LINE number needs 9 bits.

 

TAG bits = 32 - 9 - 6 = 17 bits.

To find the number of spanning trees using 2 methods:

1. If graph is complete, use n^n-2 formula
2. If graph is not complete, then use kirchhoff theorem.

Steps in Kirchoff’s Approach:

(i) Make an Adjacency matrix.

(ii) Replace all non-diagonal is by – 1.

(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.

(iv) Co-factors of any element will give the number of spanning trees.  

Using the Kirchhoff theorem will take lot of time because the number of vertices are 9. 

So, we use brute force technique to solve the problem with the help of Kruskal's algorithm.

Renaming and creating a new file requires us to search the complete inode for duplicate names (to check if the same name already exists). There is no such problem in deleting and opening a file, as duplicate names are not possible while they are created.

Let the levels be  1,2,3,4,5,6. (1 is the least difficult, 6 is the most difficult level)
Let the computers be F,M,S( fast, medium, slow).

As per the given constraint,  1 must be given to F and 6 must be given to S.
Now we are left with 2,3,4,5 and  F being assigned 1, S being assigned 6 and M being assigned none.
Another constraint is that, every computer must be assigned atleast one.
So compute with assigning one job to M, two jobs to M, three jobs to M and four jobs to M.
Assigning one job to M: we can assign 1 out of 4 jobs in (4C1 ways) and remaining 3 jobs to F,S in  2*2*2 = 8  ways. (each job has two options, either F or S),



Assigning two jobs to M: we can select two jobs from 4 in 4C2 ways and remaining 2 can be distributed to  F and S in  2*2 ways ( each job has two options either F or S)

Assigning three jobs to M: we can select 3 out of 4 in 4C3 ways remaining can be distributed to F,M in 2 ways. 

Assigning 4 jobs to M: it can be done in only one way.

Total : 4c1*8  +  4C2* 4  + 4C3*2 + 1

   = 32+24+8+1

=65

Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).

Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity. 

Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum. 

Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j. 

The number of comparisons will not take more than “n” for the given input array. 

Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity. 

Input: count=0 , i=0 and j=-3

For(j = -3; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition fails because they are given logical AND. 

So, we are not entering the “if” condition and come out of the loop. The count and “i” values remain “0”. 

For(j = -2; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition fails because they are given logical AND. 

So, we are not entering the “if” condition and come out of the loop. The count and “i” values remain “0”. 

For(j = -1; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition fails because they are given logical AND. 

So, we are not entering the “if” condition and come out of the loop. The count and “i” values remain “0”.

For(j = 0; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition TRUE then enters into the loop. 

count=0+0 → Count=0

For(j = 1; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition TRUE then enters into the loop. 

count=0+1 → Count=1

For(j = 2; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition TRUE then enters into the loop. 

count=1+2 → Count=3

For(j = 3; j <= 3; j++)   → Condition TRUE then enters into the loop. 

if((j >= 0) && (i++))   → Condition TRUE then enters into the loop. 

count=3+3 → Count=6

 

For(j = 4; j <= 3; j++)   → Condition FALSE we are not entering the loop. 

count=6+4 → We are given a condition as a post increment. So, “i” updates the next instruction. 

The above code segment executes successfully and will print value=10.

Explanation :

Probability of 1st condition being satisfied(say P(A)) = 10/15 = 2/3

Probability of 2nd condition being satisfied(say P(B)) = 1/20

Probability of both conditions being satisfied(say P(A intersection B)) = 2/3*1/20 = 1/30

Probability of any one condition being satisfied = P(A union B) = P(A)+P(B)-P(A intersection B) = 2/3 + 1/20 - 1/30 = 41/60

therefore, expected number of tuples = (41/60)*1200 = 820

L1. L2 =>  regular . CFL  == CFL. CFL  (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under concatenation so 

CFL. CFL= CFL  

Hence

Regular . CFL = CFL is true

 

L1 ∪ L2 => Regular ∪ CFL = CFL 

Regular ∪ CFL = CFL ∪ CFL  (as every regular is CFL so we can assume regular as CFL)

 

Since CFL is closed under union 

Hence Regular ∪ CFL = CFL   is true

 

L1 ∩ L2 => Regular ∩ CFL = CFL 

Regular languages are closed under intersection with any language

I.e,

Regular ∩ L = L  (where L is any language such as CFL, CSL etc)

 

Hence Regular ∩ CFL = CFL  is true

 

Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.

 

L1 − L2 => Regular − CFL = CFL 

=> Regular − CFL = regular ∩ CFL (complement)

Since CFL is not closed under complement so complement of CFL may or may not be CFL

 

Hence Regular − CFL need not be CFL

 

For ex:

R= (a+b+c)*  and L= {am bn ck | m ≠ n or n ≠ k} which is CFL.

 

The complement of L = {an bn cn | n>0} which is CSL but not CFL.

 

So 

R − L = (a+b+c)* − {am bn ck | m ≠ n or n ≠ k}

 

=> (a+b+c)* ∩  L (complement) 

=> (a+b+c)* ∩  {an bn cn | n>0}

=> {an bn cn | n>0}

 

Which is CSL. Hence Regular − CFL need not be CFL.

C2 checks the bits d1, d3, d4, d6, d7.

C2=1, d1= 1, d3= 1, d4= 0, d6= 0, d7= 1.

The number of 1s is even. So, even parity is used in this problem.

C1 checks the bits d1, d2, d4, d5, d7.

C1=0, d1= 1, d2= 0, d4= 0, d5= x, d7= 1.

As the parity used is even parity, the value of d5 should be 0.

x=d5=0

 

C8 checks the bitsa d5, d6, d7, d8.

C8=y, d5= x=0, d6= 0, d7= 1, d8= 1.

As the parity used is even parity, the value of C8 should be 0.

C8=y=0.

x=y=0.

The truth table will be

RQP	Rn Qn Pn
000	011
011	101
101	000

 

Therefore, the next three states are : 101, 000 and 011

Let assume n=512

Method-1: 

Using standard recursive algorithm:

MaxMin is a recursive algorithm that finds the maximum and minimum of the set of elements {a(i), a(i+1), ..., a(j)}. The situation of set sizes one (i=j) and two (i=j-1) are handled separately. For sets containing more than two elements, the midpoint is determined ( just as in binary search) and two new subproblems are generated. When the maxima and minima of these subproblems are determined, the two maxima are compared and the two minima are compared to achieve the solution for the entire set. 

To find the number of element comparisons needed for Maxmin, T(n) represents this number, then the resulting recurrence relation is

When n is a power of two, n = 2^k for some positive integer k, then

T(n)=2T(n/2)+2

        =2(2T(n/4)+2)+2

        =4T(n/4)+4+2

           ፧

        =2k-1T(2)+1ik-12i

        =2k-1+2k-2

        =3n/2-2 

→ The given example n=512

Apply into 3n/2 -2

= (3*512)/2 -2

= 768-2

= 766

Method-2: 

Find the minimum and maximum independently, using n-1 comparisons for each, for a total of 2n-2 comparisons. In fact, at most 3⌊n/2⌋ comparisons are sufficient to find both the minimum and the maximum. The strategy is to maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements. 

Setting up initial values for the current minimum and maximum depends on whether n is odd or even. If n is odd, we set both the minimum and maximum to the value of the first element,and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison on the first 2 elements to determine the initial values of the minimum and maximum, and then process the rest of the elements in pairs as in the case for odd n.

Let us analyze the total number of comparisons. If n is odd, then we perform 3⌊n/2⌋ comparisons. If n is even, we perform 1 initial comparison followed by 3(n-2)/2 comparisons, for a total of (3n/2)-2.  Thus, in either case, the total number of comparisons is at most 3⌊n/2⌋.

Given an even number of elements. So, 3n/2 -2 comparisons. 

= (3*512)/2 -2

= 768-2

= 766

 

Method-3:

By using Tournament Method: 

Step-1: To find the minimum element in the array will take n-1 comparisons. 

We are given 512 elements. So, to find the minimum element in the array will take 512-1= 511 

Step-2: To find the largest element in the array using the tournament method. 

1. After the first round of Tournament , there will be exactly n/2 numbers =256 that will lose the round.
2. The biggest loser (the largest number) should be among these 256 loosers.To find the largest number will take (n/2)−1 comparisons =256-1 = 255

Total 511+255= 766

The time complexity of searching an element in T that is smaller than the maximum element in T is O(1) time.

Example:

 

Comparing that 5<10 will take only a constant amount of time.