Scribd
Upload
4 views1 page

Modified Select Algorithm Recurrence Analysis

The document discusses the recurrence relations for different versions of the select algorithm, specifically focusing on modifications that involve grouping elements. It identifies the smallest values for parameters a, b, and c in the recurrence relations and concludes that the modified select algorithm has a runtime of Θ(n). Additionally, it explores the implications of these modifications on the overall time complexity of the algorithm.

Uploaded by

Mustafa Noor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Modified Select Algorithm Recurrence Analysis

The document discusses the recurrence relations for different versions of the select algorithm, specifically focusing on modifications that involve grouping elements. It identifies the smallest values for parameters a, b, and c in the recurrence relations and concludes that the modified select algorithm has a runtime of Θ(n). Additionally, it explores the implications of these modifications on the overall time complexity of the algorithm.

Uploaded by

Mustafa Noor
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Selection Reset Progress Reveal Solutions

In the select algorithm, the runtime is represented with the recurrence relation
n  
7n
T (n) = O(n) + T +T .
5 10

Here, T ( n5 ) is for selecting the pivot, and T ( 7n


10 ) is for the recursive call to select the k-th element.

Consider the modified version of the select algorithm, where we split our array into d n7 e groups of size
≤ 7 instead. What would be the recurrence relation for this modified version? Specifically, if we write
the recurrence relation as T (n) = O(n) + T ( na ) + T ( bn
c ), where a, b, and c are non-negative integers,
what are the smallest possible values of a, b, and c?
a=

Correct
b=

Correct
c=

Correct
What is the smallest exponent x such that the modified version of the select described above on an
array of size n always takes time O(nx )?

Correct
Now assume that the O(n) work per recursive step takes exactly n units of time on our machine. In
other words, suppose that the recurrence relation for the runtime is
n  
bn
T (n) = n + T +T .
a c

What is the smallest coefficient C such that we can use the substitution method to prove that the
recurrence relation for the modified select algorithm is T (n) ≤ Cn

Correct
Now consider another modified version of the select algorithm, where we split our array into dn/3e
groups of size ≤ 3 instead. What would be the recurrence relation for this modified version? Specifically,
if we write the recurrence relation as
n  
bn
T (n) = n + T +T ,
a c

where a, b, and c are non-negative integers, what are the smallest possible values of a, b, and c?
a=

Correct
b=

Correct
c=

Correct
Which one is true for the modified select recurrence relation that you came up with in the last part?
T (n) = Θ(n)
T (n) = Θ(n log n)
T (n) = Θ(n2 )
Correct

You might also like