retagged by
1,481 views
4 votes
4 votes

retagged by

1 Answer

8 votes
8 votes
Answer of this question should be

T(n) = T(2*n/3) + 1

because after split there are two possibilities

either T(n) = T(2*n/3) + 1 or T(n) = T(n/3) + 1,

because that element is either present in left side or in right side, not on both sides.

As we need to find the worst case so number of comparison holds this relation 2*n/3  > n/ 3 ,

so we take this case T(n) = T(2*n/3) + 1.
Answer:

Related questions

0 votes
0 votes
2 answers
1
ben10 asked Sep 9, 2018
827 views
0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
3
2 votes
2 votes
1 answer
4