MCQs Asymptotic Notations Worst, Average and Best Case Time Complexities

1. Let T(n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n) and for all integers n ≥ 1 . Which of the following represents the order of growth of T(n) as a function of

• O(n)
• O(n log n)
• O(n²)
• O(n³)

Ans: O(n²)

2. An all-pairs shortest-paths problem is efficiently solved using:

• Dijkstra’ algorithm
• Bellman-Ford algorithm
• Kruskal algorithm
• Floyd-Warshall algorithm

Ans: Floyd-Warshall algorithm

EXPLANATION

An all-pairs shortest-paths problem is efficiently solved using Floyd-Warshall algorithm. For more information on all-pairs shortest-paths problem and its solution using Floyd-Warshall algorithm Refer:Dynamic Programming | Set 16 (Floyd Warshall Algorithm) So, option (D) is correct.

3. The travelling salesman problem can be solved in:

• Polynomial time using dynamic programming algorithm
• Polynomial time using branch-and-bound algorithm
• Exponential time using dynamic programming algorithm or branch-and-bound algorithm
• Polynomial time using backtracking algorithm

Ans: Exponential time using dynamic programming algorithm or branch-and-bound algorithm

EXPLANATION

The travelling salesman problem can be solved in exponential time using dynamic programming algorithm or branch-and-bound algorithm. For more information on travelling salesman problem and its solution Refer:Travelling Salesman Problem So, option (C) is correct.

4. Which of the following is asymptotically smaller?

• lg(lg*n)
• lg*(lgn)
• lg(n!)
• lg*(n!)

Ans: lg(lg*n)

EXPLANATION

Options are in following order: lg(lg*n) < lg*(lgn) < lg(n!) < lg*(n!).
So, option (A) is correct.

5. Let f(n) and g(n) be asymptotically non-negative functions. Which of the following is correct?

• θ ( f (n)*g(n)) = min (f (n), g(n))
• θ ( f (n)*g(n)) = max (f (n), g(n))
• θ( f (n) + g(n)) = min (f (n), g(n))
• θ ( f (n) + g(n)) = max (f (n), g(n))

Ans: θ ( f (n) + g(n)) = max (f (n), g(n))

EXPLANATION

Case-1:
When none of the f(n) and g(n) are constant functions – In this case max(f(n) , g(n)) <= f(n) * g(n) so max(f(n), g(n)) can not provide a upper bound for f(n) * g(n).
Case-2:
When both of the f(n) & g(n) are constant functions or when any one of the f(n) and g(n) is a non zero constant function, In this case f(n) * g(n) = theta(max(f(n), g(n))).
Case-3:
When at least any one of the f(n) and g(n) is 0, In this case f(n) * g(n) != theta(max(f(n), g(n))). Since max(f(n), g(n)) COULD BE unable to give a lower bound.

Option (D) is correct.

6. Consider the following C function:

 
int f(int n)
{
   static int i = 1;
   if (n >= 5)
      return n;
   n = n+i;
   i++;
   return f(n);
}

The value returned by f(1) is

• 5
• 6
• 7
• 8

Ans: 7

EXPLANATION

See Question 3 of http://www.geeksforgeeks.org/c-language-set-2/

7. Consider the following C function.

 
int fun (int n)
{
  int x=1, k;
  if (n==1) return x;
  for (k=1; k < n; ++k)
     x = x + fun(k) * fun(n – k);
  return x;
}

The return value of fun(5) is __________.

• 0
• 26
• 51
• 71

Ans: 51

EXPLANATION

fun(5) = 1 + fun(1) * fun(4) + fun(2) * fun(3) + fun(3) * fun(2) + fun(4) * fun(1)
= 1 + 2*[fun(1)*fun(4) + fun(2)*fun(3)]
Substituting fun(1) = 1
= 1 + 2*[fun(4) + fun(2)*fun(3)]
Calculating fun(2),
fun(3) and fun(4) fun(2) = 1 + fun(1)*fun(1) = 1 + 1*1 = 2
fun(3) = 1 + 2*fun(1)*fun(2) = 1 + 2*1*2 = 5
fun(4) = 1 + 2*fun(1)*fun(3) + fun(2)*fun(2) = 1 + 2*1*5 + 2*2 = 15
Substituting values of fun(2), fun(3) and fun(4)
fun(5) = 1 + 2*[15 + 2*5] = 51

8. Consider the following recursive JAVA function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()? 

static void get (int n)
{
  if (n < 1) return;
  get(n-1);
  get(n-3);
  System.out.print(n);
}

• 15
• 25
• 35
• 45

Ans: 25

EXPLANATION

                              get(6) [25 Calls]
                              /      
               [17 Calls] get(5)       get(3) [7 Calls]
                        /     
                    get(4)    get(2)[5 Calls]
                   /     
     [7 Calls] get(3)  get(1)[3 Calls]
                /     
             get(2)   get(0)
            /    
[3 Calls]get(1)  get(-1) 
   /  
get(0) get(-2)

We can verify the same by running below program.  C/C++ Code

 
# include <stdio.h>
int count = 0;

void get (int n)
{
    count++;
    if (n < 1) return;
    get(n-1);
    get(n-3);
}
int main()
{
    get(6);
    printf("%d ", count);
}

Output: 25

9. What will be the output of the following JAVA program?  C/C++ Code

 class GFG
{
   static int d=1;
   static void count(int n)
    {
    System.out.print(n+" ");
    System.out.print(d+" ");
    d++;
    if(n > 1) count(n-1);
    System.out.print(d+" ");
  }

 public static void main(String args[])
    {
       count(3);
    }
}

• 3 1 2 2 1 3 4 4 4
• 3 1 2 1 1 1 2 2 2
• 3 1 2 2 1 3 4
• 3 1 2 1 1 1 2

Ans: 3 1 2 2 1 3 4 4 4

EXPLANATION

count(3) will print value of n and d. So 3 1 will be printed and d will become 2.
Then count(2) will be called. It will print value of n and d. So 2 2 will be printed and d will become 3.
Then count(1) will be called. It will print value of n and d. So 1 3 will be printed and d will become 4.
Now count(1) will print value of d which is 4. count(1) will finish its execution.
Then count(2) will print value of d which is 4.

Similarly, count(3) will print value of d which is 4. So series will be A.

10. The function f is defined as follows:

 
int f (int n) {
    if (n <= 1) return 1;
    else if (n % 2  ==  0) return f(n/2);
    else return f(3n - 1);
}

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.
1. The function f terminates for finitely many different values of n ≥ 1.
ii. The function f terminates for infinitely many different values of n ≥ 1.
iii. The function f does not terminate for finitely many different values of n ≥ 1.
iv. The function f does not terminate for infinitely many different values of n ≥ 1.
Which one of the following options is true of the above?

• (i) and (iii)
• (i) and (iv)
• (ii) and (iii)
• (ii) and (iv)

Ans: (ii) and (iv)

EXPLANATION

The function terminates for all values having a factor of 2 {(2.x)2==0}
So, (i) is false and (ii) is TRUE.
Let n = 3, it will terminate in 2nd iteration.
Let n=5, it will go like 5 – 14 – 7 – 20 – 10 – 5 – and now it will repeat.
And any number with a factor of 5 and 2, there are infinite recursions possible.
So, (iv) is TRUE and (iii) is false.

11. Consider the same recursive C function that takes two arguments

 
unsigned int foo(unsigned int n, unsigned int r) {
  if (n  > 0) return (n%r +  foo (n/r, r ));
  else return 0;
}

What is the return value of the function foo when it is called as foo(513, 2)?

• 9
• 8
• 5
• 2

Ans: 2

EXPLANATION

foo(513, 2) will return 1 + foo(256, 2). All subsequent recursive calls (including foo(256, 2)) will return 0 + foo(n/2, 2) except the last call foo(1, 2) .
The last call foo(1, 2) returns 1. So, the value returned by foo(513, 2) is 1 + 0 + 0…. + 0 + 1.
The function foo(n, 2) basically returns sum of bits (or count of set bits) in the number n.

12. C/C++ Code

 class GFG
{
  static int f(int a[],int i, int n)
  {
    if(n <= 0) return 0;
    else if(a[i] % 2 == 0) return a[i] + f(a, i+1, n-1);
    else return a[i] - f(a, i+1, n-1);
  }
   public static void main(String args[])
    {
      int a[] = {12, 7, 13, 4, 11, 6};
      System.out.print(f(a,0,6));
    }
}

• -9
• 5
• 15
• 19

Ans: 15

EXPLANATION

f() is a recursive function which adds f(a+1, n-1) to *a if *a is even. If *a is odd then f() subtracts f(a+1, n-1) from *a. See below recursion tree for execution of f(a, 6). .

 f(add(12), 6) /*Since 12 is first element. a contains address of 12 */
    |
    |
 12 + f(add(7), 5) /* Since 7 is the next element, a+1 contains address of 7 */
        |
        |
     7 - f(add(13), 4)
              |
              |
           13 - f(add(4), 3)
                     |
                     |
                  4 + f(add(11), 2)
                             |
                             |
                           11 - f(add(6), 1)
                                    |
                                    |
                                 6 + 0

So, the final returned value is 12 + (7 – (13 – (4 + (11 – (6 + 0))))) = 15

13. Consider the following function

 
double f(double x){
  if (abs(x*x - 3) < 0.01) return x;
  else return f(x/2 + 1.5/x);
}

Give a value q (to 2 decimals) such that f(q) will return q:_____.

• 1.73
• 2.24
• 4.22
• 3.42

Ans: 1.73

EXPLANATION

14. Consider the JAVA function given below.  C/C++ Code

  static  int f(int j)
{
   int i = 50;
  int k;
  if (i == j)
  {
    System.out.print("something");
    k = f(i);
    return 0;
  }
  else return 0;
}

Which one of the following is TRUE?

• The function returns 0 for all values of j.
• The function prints the string something for all values of j.
• The function returns 0 when j = 50.
• The function will exhaust the runtime stack or run into an infinite loop when j = 50

Ans: The function will exhaust the runtime stack or run into an infinite loop when j = 50

EXPLANATION

When j is 50, the function would call itself again and again as neither i nor j is changed inside the recursion.

15. Consider the code fragment written in JAVA below :  C/C++ Code

 void f (int n)
{ 
  if (n <=1)  {
   System.out.print(n);
  }
  else {
   f (n/2);
   System.out.print(n%2);
  }
}

What does f(173) print?

• 010110101
• 010101101
• 10110101
• 10101101

Ans: 10101101

EXPLANATION

(173)₂ = 10101101

Happy Learning – If you require any further information, feel free to contact me.