Recurrences
Question 1 
(a) Use the patterns given to prove that
(You are not permitted to employ induction)
(b) Use the result obtained in (a) to prove that
Theory Explanation. 
Question 2 
For parameters a and b, both of which are ω(1), T(n) = T(n^{1/a})+1, and T(b)=1.
Then T(n) is
θ(log_{a} log_{b} n)  
θ(log_{b} log_{a} n)
 
θ(log_{2} log_{2} n)
 
θ(log_{ab} n)

Question 2 Explanation:
T(n) = T(n^{1/a}+1, T(b) = 1
T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
Question 3 
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the nonnegative integers:
Which one of the following options is correct about the recurrence T(n)?
Which one of the following options is correct about the recurrence T(n)?
Question 3 Explanation:
Question 4 
The Lucas sequence L_{n} is defined by the recurrence relation:
L_{n} = L_{n1} + L_{n2} , for n >= 3,
with L_{1} = 1 and L_{2} = 3.
Which one of the options given is TRUE?
L_{n} = L_{n1} + L_{n2} , for n >= 3,
with L_{1} = 1 and L_{2} = 3.
Which one of the options given is TRUE?
A  
B  
C  
D 
Question 5 
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n^{2}
Which of the following statements is/are TRUE?
Which of the following statements is/are TRUE?
f ∈ O(g)  
f ∈ Ω(g)  
f ∈ o(g)  
f ∈ Θ(g) 
Question 6 
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:
Let f1(n) and f2(n) denote the number of times the statement “x = x + 1” is executed in Function 1 and Function 2, respectively. Which of the following statements is/are TRUE?
Let f1(n) and f2(n) denote the number of times the statement “x = x + 1” is executed in Function 1 and Function 2, respectively. Which of the following statements is/are TRUE?
f1(n) ε Θ(f2(n))  
f1(n) ε o(f2(n))  
f1(n) ε ω(f2(n))  
f1(n) ε O(n) 
Question 7 
The solution of the recurrence relation T(m) = T(3m/4) + 1 is :
θ(lg m)  
θ(m)  
θ(mlg m)  
θ(lglg m)

Question 7 Explanation:
Using Masters Method:
a = 1, b = 4/3, k = 0, p = 0
Here, a = b^{k}
So, T(m) = n^{log a/ log b} log^{p+1} n
T(m) = θ(log m)
a = 1, b = 4/3, k = 0, p = 0
Here, a = b^{k}
So, T(m) = n^{log a/ log b} log^{p+1} n
T(m) = θ(log m)
Question 8 
The recurrence relation capturing the optimal execution time of the towers of Hanoi problem with n discs is:
T(n)=2T(n2)+2  
T(n)=2T(n/2)+1  
T(n)=2T(n2)+n  
T(n)=2T(n1)+1 
Question 8 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2 ^{2 }T(n – 2) + 3
⋮
= 2 ^{k} T( n – k) + (2 ^{k} – 1)
n – k = 1
= 2 ^{n1} T(1) + (2^{ n1} – 1)
= 2^{ n1} + 2^{ n1} – 1
= 2 ^{n} – 1
≌ O(2 ^{n} )
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2 ^{2 }T(n – 2) + 3
⋮
= 2 ^{k} T( n – k) + (2 ^{k} – 1)
n – k = 1
= 2 ^{n1} T(1) + (2^{ n1} – 1)
= 2^{ n1} + 2^{ n1} – 1
= 2 ^{n} – 1
≌ O(2 ^{n} )
There are 8 questions to complete.