logo

Estimating the number of times lights are turned on or off using recursion and substitution method

   

Added on  2023-04-26

3 Pages547 Words151 Views
Question 1:
a.) Pseudocode for turnOn(n)
Algorithm turnOn( n )
//Lights 1... n are all off
//Final result :Lights 1... n are all on.
If(n = 1) then Turn ON light 1
//for n > = 2
else
{
If( n > 2) then turnOn( n – 2)
turn On light n
if(n > 2) then turnOff( n -1)
turnOff( n -1)
}
end
b.) The code is implemented by use of recursion and an array to keep track of the off and on lights
and print them as we power them either off or on respectively. It then generates results and
writes them in a file named LightsTestIO.txt.
c.) We are going to estimate the number of times the lights are turned off or on using the
substitution method of solving recurrences where we make a guess then use mathematical
induction to prove the guess correct or otherwise.
T(n) = 2T(n-2) + (n-1).
Let our solution be T(n)//linear time .
Now lets use induction to prove our answer.
We need to prove that T(n) <= n logn, assuming it is true for values smaller than n.
T(n)=2T(n – 2) + (n – 1) <= (n – 2) + ( n -1)
=2n -1
=n
Hence T(n).

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
Communication and Information Complexity
|8
|1309
|244

Answer to Assignment 2
|7
|826
|370

Applications to Linear Difference Equations
|11
|780
|407