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

A
Theory Explanation.
Question 2

For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.

Then T(n) is

A
θ(loga logb n)
B
θ(logb loga n)
C
θ(log2 log2 n)
D
θ(logab n)
Question 2 Explanation: 
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Question 3
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

Which one of the following options is correct about the recurrence T(n)?
A
B
C
D
Question 3 Explanation: 
Question 4
Suppose c = 〈c[0], ... , c[k – 1]〉 is an array of length k, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k – 1
do z ← z2 mod n
if c[i] = 1
then z ← (z × a) mod n
return z
If k = 4, c = 〈1, 0, 1, 1〉, a = 2 and n = 8, then the output of DOSOMETHING(c, a, n) is
A
0
B
1
C
2
D
3
Question 5

The equality above remains correct if X is replace by
A
Only I
B
Only II
C
I or III or IV but not II
D
II or III or IV but not I
Question 6
The Lucas sequence Ln is defined by the recurrence relation:
Ln = Ln-1 + Ln-2 , for n >= 3,
with L1 = 1 and L2 = 3.
Which one of the options given is TRUE?
A
A
B
B
C
C
D
D
Question 7
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n2
Which of the following statements is/are TRUE?
A
f ∈ O(g)
B
f ∈ Ω(g)
C
f ∈ o(g)
D
f ∈ Θ(g)
Question 8
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?
A
f1(n) ε Θ(f2(n))
B
f1(n) ε o(f2(n))
C
f1(n) ε ω(f2(n))
D
f1(n) ε O(n)
There are 8 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access