321 views
0 votes
0 votes

how to approach this type of question suggest me please

2 Answers

Best answer
0 votes
0 votes

"here the key thing is that always choose the highest or smallest element as pivot so that recurrence relation become

T(n)=T(n-1)+O(n) it will lead to worst case time complexity."

 

break down the question for smaller problem and observe the pattern.

for array of size 3

3 1 2

 

here in worst case the pivot selection may follow the order:

1-> 3-> 2.    

1-> 2-> 3.

3-> 2-> 1

3-> 1-> 2

so total 4 list orderings are possible (i.e. {2->3->1} {3->2->1} { 1->2->3}  {2->1->3}) i.e.$2^{n-1}$ (n is number of elements in array)

for array of size 4:

4 1 3 2

 

pivot selection can be done in following 8 ways for worst case:

1->2->3->4

1->4->3->2

1->4->2->3

1->2->4->3

4->3->2->1

4->3->1->2

4->1->3->2

4->1->2->3

total $2^{n-1}$     $2^{4-1}$=8

so for 7 elements we have $2^{7-1}$=64 ordering possible.

P.S.- as we have 3 elements so for 1st pivot we have 2 choices   next one we have 2 choices and the last one will be included automatically so in similar way for n distinct elements we have 2*2*2*2...........(n-1)times orderings

 

selected by
0 votes
0 votes
From n elements till 2 elements in the partition list, we can choose either the min or max term as pivot and call partition for the remaining list. therefore, for each iteration(n till 2 both inclusive => n-1 iterations) of partition list of size between n to 2, we have two choices. So, the no. of such sequence of selecting pivot becomes-

$2^{n-1} = 2^{7-1} = 2^6 = {\color{Red} {64}}$

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
3
amitarp818 asked Nov 18, 2023
223 views
Given L1 = {a*baa*} and L2 = {ab*}The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by