consider the following program where the argument n is a power of 2.The algorith
ID: 3543946 • Letter: C
Question
consider the following program where the argument n is a power of 2.The algorithm does not do anything useful.
DO-NOTHING(n)
if n == 1
return 1
for i = 1 to 8
z = DO-NOTHING(n=2)
for i = 1 to n^3
z = 0
(1) Let T (n), the number of times the attribute is z = 0 is executed. Type a recurrence that defines T(n)
(2) exchange line"8" for "7" in the algorithm,if S(n) is the number of times the attribute z = 0is executed in this new algorithm. The class O belongs to S (n)? Give
fairest possible answer and justify it without using the Master Theorem.
Explanation / Answer
a>
0
as z = DO-NOTHING(n=2)
always recurcively send n=2 and it will go on
b>
0
as z = DO-NOTHING(n=2)
always recurcively send n=2 and it will go on
no effect on changing the position
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.