Asymptotic-Complexity

Question 1

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
A

f2, f3, f1

B
f3, f2, f1
C
f2, f1, f3
D
f1, f2, f3
AlgorithmsAsymptotic-ComplexityGATE 2021 CS-Set-1Video-Explanation
Question 1 Explanation: 

The asymptotic notation order should be 

Constant < logarithmic < linear < polynomial < exponential < factorial 

F2 and F3 → Polynomial 

F1 → Exponential

By the order of asymptotic notations F1 is definitely larger. 

Method-1: 

Consider n=100

F1 : 100 ^100 ⇒ 1.e+200

F2 : N^log(100) base 2 ⇒  100 ^ log(100) base 2 ⇒ 100^6.6438561897747 = 1,93,96,00,91,15,564.181300016469223466

F3 : N^Sqrt(n) ====> 100^Sqrt(100) ⇒ 100^10 ⇒ 10,00,00,00,00,00,00,00,00,000

Method-2:

We can apply "log" on both sides. 

log(F1)=nlog10 (base 2)

log(F2)=(logn)^2 = logn * logn (base 2)

log(F3)=sqrt(n)logn (base 2) 

Answer: F2< F3< F1

Question 2

Consider the following recursive function: 

 function fib (1:integer);integer;
 begin
 if (n=0) or (n=1) then fib:=1
 else fib:=fib(n-1) + fib(n-2)
 end;

The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.

A
Theory Explanation.
AlgorithmsAsymptotic-ComplexityGATE 1994
Question 3

An array A contains n integers in locations A[0],A[1], …………… A[n-1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n-1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared. 

 min:=n;
 i=0;
 while _____do
 begin
     temp:=A[i];
     j:=i;
     while _____do
 begin
     A[j]:=_____;
     j:=(j+K) mod n;
 if j
A
Theory Explanation.
AlgorithmsAsymptotic-ComplexityGATE 1994
Question 4

Consider the following two functions:

Which of the following is true?

A
g1(n) is O(g2(n))
B
g1 (n) is O(3)
C
g2 (n) is O(g1 (n))
D
g2 (n) is O(n)
E
Both A and B
AlgorithmsAsymptotic-ComplexityGATE 1994
Question 4 Explanation: 
In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Question 5

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

f1(n)=2n     f2(n)=n3/2     f3(n)=n log2 n     f4(n)=nlog2n
A
f3, f2, f4, f1
B
f3, f2, f1, f4
C
f2, f3, f1, f4
D
f2, f3, f4, f1
AlgorithmsAsymptotic-ComplexityGATE 2011
Question 5 Explanation: 
If they are expecting to find an asymptotic complexity functions means
→ Divide functions into 2 categories
1. Polynomial functions
2. Exponential functions
Above 4 functions we have only one exponential function is f1 (n) = 2n . So, It’s value is higher than to rest of the functions.
Substitute log on both sides then we get an ascending order is f3, f2, f4.
Question 6
Consider the following recurrence:

Then, which of the following statements is/are TRUE?
A
f (2^ n -1) 2^ n -1
B
f (2 ^n ) 1
C
f (5 . 2 ^n ) 2^ n + 1 1
D
f (2^ n + 1) 2 ^n + 1
AlgorithmsAsymptotic-ComplexityGATE 2022Video-Explanation
Question 6 Explanation: 
We can solve this problem by eliminating options. Substitute n=1024
Based on the “n” value we can get Option-A, B and C are correct.
Question 7
Which one of the following statements is TRUE for all positive functions f (n) ?
A
f ( n ^2 ) ( f ( n ) ^2 ), when f ( n ) is a polynomial
B
f ( n ^2 ) o ( f ( n ) ^2 )
C
f ( n ^2 ) O ( f ( n ) ^2 ), when f ( n ) is an exponential function
D
AlgorithmsAsymptotic-ComplexityGATE 2022Video-Explanation
Question 7 Explanation: 
constant < logarithmic < linear < polynomial < exponential < factorial
f(n)=n^c where c is a constant
f(n^2) = (n^2)^c = n^2c
(f(n))^2 = (n^c)^2 = n^2c
f(n^2) = (f(n))^2 is TRUE asymptotically.
Option-B: FALSE: The small omega function indicates the tightest upper bound.
f(n)^2 < o(f(n)^2) is FALSE asymptotically.
Option-C: FALSE: Consider f(n)=logn
f(n^2)=logn^2 = 2*logn
(f(n))^2 = (logn)^2 = logn * logn
f(n^2) <=Ω(f(n))^2 is FALSE asymptotically.
Option-D: FALSE:
Exponential values(Eg: 2^n, 3^n,..,k^n where k is a constant ”
f(n)=3^n
f(n^2)=f(3^(n^2)
(f(n))^2 = (3^n)^2 = 3^2n
f(n^2) >= O(f(n))^2 is FALSE asymptotically.
Question 8

Consider the following functions from positives integers to real numbers

 

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

A
B
C
D
AlgorithmsAsymptotic-ComplexityGATE 2017 [Set-1]Video-Explanation
Question 8 Explanation: 
In this problem, they are expecting to find us “increasing order of asymptotic complexity”.
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 9
Let f(n) = n and g(n) = n(1+sin n), where n is a positive integer. Which of the following statements is/are correct?
I. f(n) = O(g(n))
II. f(n) = Ω(g(n))
A
Only I
B
Only II
C
Both I and II
D
Neither I nor II
AlgorithmsAsymptotic-ComplexityGATE 2015 [Set-3]Video-Explanation
Question 10
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of n) asymptotically?
A
a
B
b
C
c
D
d
E
e
AlgorithmsAsymptotic-ComplexityTIFR PHD CS & SS 2020
There are 10 questions to complete.

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

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