The Gateway to Computer Science Excellence
+3 votes

in Algorithms by Boss (11.9k points)
edited by | 508 views
yes, it should be T(n) = T(2n/3) + 1
  1. i think T(n)=T(2n/3)+1
in quick sort if you take 9-to-1 split then

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.

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)..

1 Answer

+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.
by (131 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,832 questions
57,686 answers
107,195 users