yes, it should be T(n) = T(2n/3) + 1

The Gateway to Computer Science Excellence

+3 votes

0

I think its recurrence relation should be T(n) = T(2n/3) + T(n/3) + c.

So every time it gets splits into two-thirds and one-third.

So every time it gets splits into two-thirds and one-third.

+3

@Shubhanshu

in binary search, at every iteration we will throw away half array depending on(key<=A[mid] or key>A[mid]),

so the worst case recurrence relation will be T(n) = T(2n/3) + 1

you are taking T(n) = T(2n/3) + T(n/3) + c., which is not correct because if we choose to take T(2n/3), then we will throw away T(n/3), similiarly if we choose to take T(n/3), we will throw away T(2n/3)..

in binary search, at every iteration we will throw away half array depending on(key<=A[mid] or key>A[mid]),

so the worst case recurrence relation will be T(n) = T(2n/3) + 1

you are taking T(n) = T(2n/3) + T(n/3) + c., which is not correct because if we choose to take T(2n/3), then we will throw away T(n/3), similiarly if we choose to take T(n/3), we will throw away T(2n/3)..

+6 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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,832 questions

57,686 answers

199,271 comments

107,195 users