Q1- Consider the following two functions.
Which of the following is true?
(a) f(n) is O(n3)
(b) g(n) is O(n2)
(c) g(n) is O(n3)
(d) O(f(n)) is same as O(g(n))
(b), (d)
If n becomes very large > 10,000, then f(n) becomes O(n2), g(n) becomes O(n2). It means b and d are the solutions.
Q2- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)= 2T(⌊n/2⌋+ √n, for n≥2,
        1,    for n=1
The time complexity of the algorithm is
(a) O(√n)
(b) O(n)
(c) O(log(n))
(d) None
(b)
By applying master’s theorem, we have O(n).
Q3- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)= n, for n ≤3,
T(n/3)+cn, otherwise
The time complexity of the algorithm is
(a) O(√n)
(b) O(n)
(c) O(log(n))
(d) O(n2)
(b)
for large n, apply master’s theorem.
Compiling time = n^logba = n^log31 = n0 = 1
Running time = c.n = n
Running time is greater than compiling time, so running time is the answer that is O(n).
Q4- What is the time complexity of the recurrence equation T(n) = 4T(n/2) + n3 ?
(a) θ(n)
(b) θ(n3)
(c) θ(nlogn)
(d) θ(n2logn)
(b)
Applying master’s theorem,
Compiling time = n^log24 = n2
Running time = n3
Running time is bigger so n3 is the answer.
Q5- Time complexity of T(n) = T(2n/3) + 1
(a) θ(n)
(b) θ(1)
(c) θ(logn)
(d) θ(n2/3)
(c)
Applying master’s theorem,
Compiling time = n^log32 = n0 = 1
Running time = 1
Both are same so answer will be (running time)*log(n) which is equal to θ(logn).