Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

26 The concept of order (Big O) is important because

27 What is the generating function G(z) for the sequence of Fibonacci numbers?

Assuming Fibonacci Sequence as :- 1, 1, 2, 3, 5, 8, 13, ......
So, sequence a_n = 1,1,2,3,5,8,13,… where, n=0,1,2,3,…
Now, The Generating Function for the sequence a_n of real numbers is defined as:

So, For the given Fibonacci Series :-
⇒ G(z) = 1+z+2z²+3z³+5z⁴+8z⁵+13z⁶+...+f_nzⁿ+... →(1)
Now , Shift one position right and multiply by 'z' :-
⇒ zG(z) = z+z²+2z³+3z⁴+5z⁵+8z⁶+... →(2)
Now, Shift one more position right and multiply by 'z' :-
⇒ z²G(z)=z²+z³+2z⁴+3z⁵+5z⁶+8z⁷+... →(3)
Now, Add Equation(2) and Equation(3) :-
⇒ zG(z)+z²G(z)=z+2z²+3z³+5z⁴+8z⁵+13z⁶+...
⇒ zG(z)+z²G(z)=G(z)−1 (From(1))
⇒ G(z)−zG(z)−z²G(z)=1
⇒

So,Generating Function for the given Fibonacci Series is:−

28 Which of the following is false?

(A)

Here 100 is constant so we can say both function are equal .
Hence it is true.
(B) √(logn) = O(log logn)
growth rate of √(logn) is greater then loglogn so it is false.
(C) If 0 < x < y then n^x = O(n^y) is always true.
(D) 2n ≠ O(nk)
if k is constant then this statement is false but here nothing is mentioned about K.

29 The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

Algo for concatenation is ⇒
{
t₁ = S₁ → nxt ;
t₂ = S₂ → nxt ;
t₁ → nxt = S₂
t₂ → nxt = S₁
S₁ → nxt = t₂
S₂ → nxt = t₁
}
it is sequential alqoni them so complexity is O(1)

30 Let f (n) = n² logn and g(n) = n(logn)¹⁰ be two positive functions of n. Which of the following statements is correct?

f(n) = n² logn
g(n) = n (logn)¹⁰
Here we can remove common factor from both the function to simply the value of f(n) & g(n)
So f(n) = n
g(n) = (logn)⁹
Now choose the largest value of n to compare both the function.
if n = 2¹⁰⁰ then f(n) = 2¹⁰⁰
g(n) = (100)⁹
f(n) > g(n).