Selection
ResetProgress
RevealSolutions
Inthe
select
algo
rithm,
the
runtime
is
rep
resented
with
the
recurrence
relation
T
(
n
)=
O
(
n
)+
T
n
5
+
T
7
n
10
.
Here,
T
(
n
5
)
isfo
r
selecting
the
pivot,
and
T
(
7
n
10
)
isfo
r
the
recursive
call
to
select
the
k
-thelement.
Consider
the
modified
version
of
the
select
algo
rithm,
where
w
e
split
our
a
rra
y
into
n
7
groupsof
size
≤
7
instead.What
w
ould
be
the
recurrence
relation
fo
r
this
modified
version?
Specifically
,
if
w
e
write
the
recurrence
relation
as
T
(
n
)=
O
(
n
)+
T
(
n
a
)+
T
(
bn
c
)
,where
a
,
b
,and
c
are
non-negative
integers,
what
a
re
the
smallest
possible
values
of
a
,
b
,and
c
?
a
=
7
Correct
5
Correct
7
Correct
1
Correct
a
+
T
bn
c
.
Whatis
the
smallest
coefficient
C
suchthat
w
e
can
use
the
substitution
method
to
p
rove
that
the
recurrence
relation
fo
r
the
modified
select
algo
rithm
is
T
(
n
)
≤
Cn
7
Correct
a
+
T
bn
c
,
where
a
,
b
,and
c
are
non-negative
integers,
what
a
re
the
smallest
possible
values
of
a
,
b
,and
c
?
a
=
3
Correct
2
Correct
3
Correct
T
(
n
)=
Θ(
n
)
T
(
n
)=
Θ(
n
log
n
)
T
(
n
)=
Θ(
n
2
)
Correct
b
=
c
=
Whatis
the
smallest
exponent
x
suchthat
the
modified
version
of
the
select
described
above
on
an
a
rra
y
of
size
n
alwa
ys
tak
es
time
O
(
n
x
)
?
Now
assume
that
the
O
(
n
)
wo
rk
per
recursive
step
tak
es
exactly
n
unitsof
time
on
our
machine.
In
other
w
o
rds,
suppose
that
the
recurrence
relation
fo
r
the
runtime
is
T
(
n
)=
n
+
T
n
Now
consider
another
modified
version
of
the
select
algo
rithm,
where
w
e
split
our
a
rra
y
into
n/
3
groupsof
size
≤
3
instead.What
w
ould
be
the
recurrence
relation
fo
r
this
modified
version?
Specifi-
cally
,
if
w
e
write
the
recurrence
relation
as
T
(
n
)=
n
+
T
n
b
=
c
=
Whichone
is
true
fo
r
the
modified
select
recurrence
relation
that
y
ou
came
up
with
in
the
last
pa
rt?