Question 1

What is time complexity of fun()?

int fun(int n)
{
  int count = 0;
  for (int i = 0; i &lt; n; i++)
     for (int j = i; j &gt; 0; j--)
        count = count + 1;
  return count;
}

time complexity of function

$\theta(n^2)$
$\theta(nlogn)$
$\theta(n)$
$\theta(logn)^2$

Answer

Correct Option: A

Question 2

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

running time of algorithm

A(n) = $\Omega$ W(n)
A(n) = $O$ W(n)
A(n) = $\Theta$ W(n)
A(n) = o W(n)

Answer

Correct Option: B

Question 3

What is time complexity for the following function?

public void printAllPossibleOrderedPairs ( int[] arrayOfItems)
{  
   for (int firstItem : arrayOfItems)
   { 
       for (int secondItem : arrayOfItems)
       {
           int[] orderedPair = new int[] { firstItem, secondItem};
           system.out.print( Arrays.toString(orderedPair));
       }
   }
}

$O (n)$
$O (n logn)$
$O (n^2)$
$O (logn)^2$

Answer

Correct Option: C

Question 4

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)
{
    if (n &lt;= 1) return n;
    return 2*fun1(n-1);
}

int fun2(int n)
{
    if (n &lt;= 1) return n;
    return fun2(n-1) + fun2(n-1);
}

time complexity of function

$O(2^n)$ for both fun1() and fun2()
$O(n)$ for fun1() and $O(2^n)$ for fun2()
$O(2^n)$ for fun1() and $O(n)$ for fun2()
$O(n)$ for both fun1() and fun2()

Answer

Correct Option: B

Question 5

What is not true about insertion sort?

Exhibits the worst case performance when the initial array is sorted in reverse order.
Worst case and average case performance is Ο(n2)
Can be compared to the way a card player arranges his card from a card deck.
None of the above!

Answer

Correct Option: D

Question 6

If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?

time complexity of queue

$O(n), O(1)$
$O(1), O(1)$
$O(1), O(n)$
$O(n), \theta(1)$

Answer

Correct Option: B

Question 7

For a binary search algorithm to work, it is necessary that the array (list) must be

binary search

sorted
unsorted
in a heap
popped out of stack

Answer

Correct Option: A

Question 8

What is the worst case run-time complexity of binary search algorithm?

$Ο(n^2)$
$O(log_2n)$
$O(n logn)$
$O(log logn)$

Answer

Correct Option: B

Question 9

Recursion uses more memory space than iteration because

It uses stack instead of queue.
Every recursive call has to be stored.
Both 1 & 2 are true.
None of the above are true.

Answer

Correct Option: B

Question 10

The number of passes needed to sort the numbers 8, 22, 7, 9, 31 in ascending order, using insertion sort is

5
4
6
3

Answer

Correct Option: D

Description: Time complexity is used for analyzing sorting functions, recursive calculations and things which generally take more computing time. This quiz will test you on this knowledge of calculating time complexity of algorithms.
Number of Questions: 10
Created by: Swati Sharma
Tags: analysis of algorithms aoa time complexity of algorithms

Test on time complexity

Find more quizzes from top tags